2

我有一个数组 A=[a1,a2,a3,a4,a5...] 我想找到数组的两个元素，比如 A[i] 和 A[j] 使得 i 小于 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
4

4 回答 4

2

您的代码可以稍微更新一下：

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-25T02:19:01.240 回答
1

使用itertools成对配方：

>>> 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-25T05:49:29.997 回答
0

不知道为什么排序。您可以调整此伪代码。

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-25T02:13:18.643 回答
0

这是另一种方法，使用更多的可迭代对象并且更多地依赖默认值：

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-25T02:23:33.003 回答