找到最小的差异

我有一个数组A = [a1，a2，a3，a4，a5 ...]，我想找到数组的两个元素，比如说A [i]和A [j]小于j并且A [j] -A [i]是最小的。找到最小的差异

请问这代码做的工作：

def findMinDifference(A): 
    Unsorted=[] 
    minDiff=1000000 
    Unsorted=A 
    Sorted=quickSort(A) 
    for i in range(0,len(Sorted)): 
     if i>=1: 
     SmallElement=Sorted[i-1] 
     indexOfSmaller=Unsorted.index(SmallElement) 
     BigElement=Sorted[i] 
     indexOfBig=Unsorted.index(BigElement) 
     if indexOfSmaller<inexOfBig: 
      diff=Sorted[i]-Sorted[i-1] 
      if diff<minDiff: 
       minDiff=diff 
    return minDiff

来源

2013-03-25 user2205925

我想你可以通过测试的代码回答你自己的问题。 – Blender 2013-03-25 02:06:23

除此之外：很难说（而且格式已经被编辑），但是你的缩进对我来说看起来很奇怪，这有时候是原文中混合了制表符和空格的标志。以防万一，你可能想用'python -tt your_program_name.py'来运行你的代码来检查不一致的空白。 – DSM 2013-03-25 02:14:18

@Blender你对算法的正确性有任何想法吗？ – user2205925 2013-03-25 02:52:57

不知道为什么排序。你可以修改这个伪代码。

for i = 0; i < array.length; i++ 
    for j = i + 1; j < array.length; j++ 
     if a[j] - a[i] < min 
      min = a[j] - a[i] 
return min

来源

2013-03-25 02:13:18

也许他想要得到一个积极的最小差异。 – Scy 2013-03-25 02:25:19

差异不一定是正面的，但运行时间必须是O（nlog（n））而不是O（n^2）。我的方法会在O（nlog（n））运行时中给出正确答案吗？ – user2205925 2013-03-25 02:50:21

好点，我现在还不清楚，在一家餐厅喝酒:)但这看起来像是一个单元测试车库的好例子。如果你的方法是*正确的*它似乎是O（n * log（n）） – 2013-03-25 04:04:13

您的代码可以被更新比特：

a = [1,2,5,9,10,20,21,45] 
a, size = sorted(a), len(a) 

res = [a[i + 1] - a[i] for i in xrange(size) if i+1 < size] 

print "MinDiff: {0}, MaxDiff: {1}.".format(min(res), max(res))

在两个字 - 寻找最小或最大差异可以简化为得到一个列表的那个包括对于每一对的差异最小/最大元件从值

来源

2013-03-25 02:19:01

的原始排序的列表中的元素的这是另一种方法，使用更多iterables更依赖于缺省：

from itertools import imap, islice, izip 

def find_min_diff(iterable, sort_func=sorted): 
    sorted_iterable = sort_func(iterable) 
    return min(imap(
     lambda a, b: b - a, 
     izip(sorted_iterable, islice(sorted_iterable, 1)), 
    ))

来源

2013-03-25 02:23:33 Tadeck

这似乎很好，但我的方法会在O（nlog（n））运行时给出正确的答案吗？ – user2205925 2013-03-25 02:51:20

使用itertools pairwise配方：

>>> from itertools import tee, izip 
>>> def pairwise(iterable): 
     "s -> (s0,s1), (s1,s2), (s2, s3), ..." 
     a, b = tee(iterable) 
     next(b, None) 
     return izip(a, b) 

>>> nums = [1, 3, 7, 13, 9, 18, 22] 
>>> min(pairwise(sorted(nums)), key=lambda x: x[1] - x[0]) 
(1, 3)

来源

2013-03-25 05:49:29 jamylak

找到最小的差异

回答

相关问题