найти минимальную разницу

Question

У меня есть массив 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 

Answer 1

Не знаю, почему-то. Вы можете адаптировать этот псевдокод.

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 

Answer 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)) 

В двух словах - поиск мин или макс дифф можно упростить получение мин/макс элемент списка, которые состоят из разностей для каждой пары элементов из отсортированного исходного списка значений

Answer 3

Это еще один подход, используя более итерируемых и более полагаться на значения по умолчанию:

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)), 
    )) 

Answer 4

Использование 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)