Как проверить ближайшие к заданному значения?

Question

[Михаил]

Здравствуйте,
есть лист к примеру

a = [56,34,25,43,21,65,23,56,23,54]
потом приходит на вход какое то число и надо взять первые 10 чисел которые ближе всего к образцу причем как слева так и справа от него, сеты не вариант потому что они удаляют дубликаты
вопрос - как??

Answer 1

[ColdSpirit]

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

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

Самое интересное что в вашем случае ближайшие 10 - это весь представленный массив =)

Comments

[Михаил]

придется по ходу делать весами, ну то есть рецтингом по вашему

Answer 2

[zooks]

А что если отсортировать массив, а затем взять 5 чисел слева и пять справа от заданного числа?

Comments

[Михаил]

в том что надо всего 10 чисел ближайших и в зависимоти от "близкости"могут быть 4 слева и 6 справа или 1 справа а 9 слева например [1,2,3,4,6,7,8,12,23,23,52,252] а контрльное число 10 вот и получается что входят все что слева и 2 справа)

[ColdSpirit]

Михаил: зато, если у вас очень много чисел, то проверок на вес будет меньше в разы

[Михаил]

вы не ппоняли вопроса)

Answer 3

[neomichi]

если изначально хранить не как список, а как двоичное дерево, то можно достичь хороших скоростей
p.s. Поиск O(log n) . Вставка, O(log n). Удаление, O(log n)