2

私は配列 A=[a1,a2,a3,a4,a5...] を持っていて、配列の 2 つの要素、たとえば 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

これは別のアプローチであり、より多くのイテラブルを使用し、デフォルトにさらに依存しています。

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 に答える
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 に答える