找到最小的差異

我有一個數組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

找到最小的差異

回答

相關問題