Разность элементов массива

Question

[Сослан Алдатов]

Добрый день!

Есть вопрос, на который никак не могу найти ответ.
Итак, есть список чисел, количество их не определено заранее.
Необходимо узнать, есть ли в этом списке как минимум три числа, разница между которыми не превышает заранее указанного значения.
Итак, вопрос в том, как это можно сделать.

Спасибо за внимание!

Answer 1

[Владлен Грачев]

Отсортировать, затем последовательно смотреть массив на соответствие условию. Если нужно, чтобы суммарная разница между числами не превышала указанного значения, то делать цикл от 0 до n-2, в котором сравнивать a[i] c a[i+2]. При a[i-2]-a[i] <= m возвращать True, после цикла — False. (n - номер последнего элемента массива (размер массива), m - заданное число, которое нужно не превышать, i - счетчик).

Реализовать, надеюсь, труда не составит?

Comments

[Сослан Алдатов]

Похоже, я не совсем верно выразил желаемое.
Речь шла не о суммарной разнице, а о попарной разнице элементов. Ну да ладно, задачу я решил, по сути, тем же последовательным перебором...хотелось найти более изящное решение, ну да что уж там.
Спасибо огромное за то, что обратили внимание на вопрос!

[Mrrl]

Здесь может быть проблема с "количество не определено заранее". Обычно это означает, что числа нельзя сохранить в массив (а тем более, отсортировать его). К сожалению, эту задачу конечным автоматом решить нельзя. А если хочется обрабатывать числа по одному и сообщить, когда нужные три числа появятся, то пригодилось бы какое-нибудь дерево поиска.

[Владлен Грачев]

@Mrrl, обратите внимание на заголовок вопроса.
@supporteam, ну, условие не сильно усложняется. Предполагал и такой вариант, просто написал о чуть более общем. Тут возвращать True при (a[i-1]-a[i] <= m && a[i-2]-a[i-1] <= m), например. Не думаю, что это задача, в которой стоит искать еще более изящное решение.