нахождение минимальной разницы

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

python arrays sorting algorithm minimum
person user2205925    schedule 25.03.2013    source источник
comment
Я думаю, вы можете ответить на свой вопрос, протестировав этот код.   -  person Blender    schedule 25.03.2013
comment
Кроме того: трудно сказать (и с тех пор форматирование было отредактировано), но ваш отступ кажется мне странным, и иногда это признак смешанных табуляций и пробелов в оригинале. На всякий случай вы можете запустить свой код, используя python -tt your_program_name.py, чтобы проверить наличие несовместимых пробелов.   -  person DSM    schedule 25.03.2013
comment
@Blender у тебя есть мысли о правильности алгоритма?   -  person user2205925    schedule 25.03.2013
comment
@ user220595 используйте minDif = float('inf'). Проверка .index() имеет стоимость O(N), поэтому ваш алгоритм будет очень медленным для больших списков. O(n^2) Я верю.   -  person jamylak    schedule 25.03.2013
comment
Также используйте имена переменных в нижнем регистре, пожалуйста. python.org/dev/peps/pep-0008 Также в зависимости от вашего реализация быстрой сортировки, ваш алгоритм может быть даже медленнее, но я не уверен   -  person jamylak    schedule 25.03.2013

Ответы (4)


arrow_upward
2
arrow_downward

Ваш код можно немного обновить:

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

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

person Artsiom Rudzenka    schedule 25.03.2013

arrow_upward
1
arrow_downward

Используя рецепт 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)
person jamylak    schedule 25.03.2013

arrow_upward
0
arrow_downward

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

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
person David Williams    schedule 25.03.2013
comment
Может быть, он хочет получить положительную минимальную разницу. - person Scy; 25.03.2013
comment
Разница не обязательно должна быть положительной, но время выполнения должно быть O(nlog(n)) не O(n^2). Даст ли мой подход правильный ответ в среде выполнения O (nlog (n))? - person user2205925; 25.03.2013
comment
Хороший момент, неясный для меня прямо сейчас, в ресторане и выпивке :) Но это похоже на отличный случай для множества модульных тестов. Если ваш подход ПРАВИЛЬНЫЙ, он выглядит как O(n*log(n)) - person David Williams; 25.03.2013
comment
@DavidWilliams Это не O (n log (n)). Смотрите мой комментарий выше - person jamylak; 25.03.2013

arrow_upward
0
arrow_downward

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

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)),
    ))
person Tadeck    schedule 25.03.2013
comment
Кажется, это хорошо, но даст ли мой подход правильный ответ в среде выполнения O (nlog (n))? - person user2205925; 25.03.2013