Быстрый алгоритм поиска следующего наименьшего и наибольшего числа в наборе

Question

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

Мотивация: у меня есть куча данных в хэш-карте с указанием дат. У меня нет даты на каждую дату. Если у меня есть данные, скажем, 10/01/2000 как 60 и 10/05/2000 как 68, и я прошу 10/02/2000, я хочу линейно интерполировать. Я должен получить 62.

Answer 1

Зависит от того, отсортирован ли ваш набор.

Если ваш набор не отсортирован, то поиск ближайшего (выше и ниже) - это операция O (n) и довольно простой алгоритм.

Если ваш набор отсортирован, то вы можете использовать модифицированный поиск пополам, чтобы найти ответ в O (log n), что, очевидно, намного лучше, особенно на больших наборах.

Если вы делаете это многократно, возможно, стоит отсортировать набор, что повлечет за собой затраты O (n log n), которые могут быть однократно или нет в зависимости от того, как часто меняется набор. Некоторые виды сортировки деревьев могут помочь улучшить сортировку в будущем при добавлении новых элементов.

Answer 2

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

1. Сортированный контейнер
   Если вы храните свои номера в отсортированном контейнере, это довольно просто. Вместо использования HashMap поместите данные в TreeMap, тогда вы сможете эффективно найти следующий более низкий или следующий более высокий элемент. В Java даже есть методы, которые делают именно то, что вы хотите:

   • higherKey(K)
   • lowerKey(K)

   Это эффективно, потому что TreeMap использует красно-черное дерево (разновидность сбалансированного двоичного дерева поиска ) внутри. higherKey и lowerKey просто начинают с корня и пересекают дерево, чтобы найти, куда должен идти ваш элемент.

   Я не уверен, какой язык вы используете, но в C ++ вы бы использовали std::map, и аналогичные методы:

   • iterator lower_bound(const key_type& k)
   • iterator upper_bound(const key_type& k)

2. Массив + сортировка
   Если вы не хотите, чтобы ваши данные постоянно сортировались, вы всегда можете сбросить данные в массив (или в любой контейнер произвольного доступа), использовать sort, а затем использовать двоичный поиск в STL. подпрограммы в массиве:

   • lower_bound
   • upper_bound

   В Java аналогом было бы создание дампов в ArrayList, вызов Java sort(), затем использование binarySearch () .

Все процедуры поиска здесь O (logn) время. Стоимость хранения ваших данных составляет O (nlogn) с отсортированным контейнером или с массивом. С отсортированным контейнером стоимость амортизируется по n вставкам; с массивом вы платите все сразу, когда звоните sort().

Если вы вообще не хотите сортировать вещи, вы всегда можете использовать линейный поиск , но вы будете платить, если будете много использовать, так как это O (n) алгоритм.

Answer 3

Сохраняйте ваш набор в виде отсортированного списка / массива и выполняйте поиск по разделам: например, в Python отсортированный список и модуль bisect из стандартной библиотеки Python соответствуют вашим потребностям.

Answer 4

Преобразовать набор в список и отсортировать его, а затем выполнить двоичный поиск числа, которого нет в наборе. Результатом будет точка вставки, то есть позиция, в которой будет присутствовать число, если оно там будет. Если вы называете это n, то элемент с индексом n отсортированного списка является следующим наименьшим числом, а элемент с индексом n+1 отсортированного списка является следующим наибольшим числом.

Вы также можете сделать это, сохраняя набор в отсортированном порядке по мере его создания, тогда поиск точки вставки станет простым делом. Этот подход используется, например, floorEntry () и ceilingEntry () методов Java TreeMap.

Answer 5

Сортируйте числа, затем выполните двоичный поиск по каждому ключу, чтобы разделить набор. Затем вы можете найти, какие цифры находятся по обе стороны от вашего пропавшего ключа.

Answer 6

Поместите свои элементы данных в дерево, например, AVL дерево, красно-черное дерево или дерево B + / B-. Затем вы можете искать упорядоченные значения.

Answer 7

Если вы знаете, что всегда будет точка данных, скажем, каждую неделю, тогда оставьте HashMap как есть и делайте то, что вы предлагаете ... Это будет операция с постоянным временем, так как вы будете делать 14 поисков в хеш-таблице (по 7 дней с каждой стороны от даты поиска), каждый из которых выполняет O (1) примитивных операций.

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

Answer 8

Нахождение n-го элемента в несортированном множестве - O (n). ( Выбрать алгоритм ) Хотя здесь вы можете свести его к более простому, менее общему алгоритму, если вам всегда нужны самые маленькие и следующие самые маленькие элементы. Но в общем случае поиск наименьшего, второго наименьшего и т. Д. Элемента в несортированном списке - это O (n). (Тебе следовало бы научить этому в своем классе алгоритмов ...)

Сортировка набора и последующая индексация элемента O (n log n)

Нахождение элемента в отсортированном наборе - O (log n) (двоичный поиск)

Answer 9

Если вы получаете ключи в массиве, вы можете отсортировать массив и найти индекс последнего элемента, который меньше требуемого элемента. Затем вы узнаете индекс ключа непосредственно перед желаемой точкой, а следующий после него элемент - тот, который непосредственно после.

Это должно дать вам достаточно для интерполяции.

(Используемая структура данных не обязательно должна быть массивом, все, что будет сортироваться, будет в порядке. Сбалансированное двоичное дерево, как предлагают другие, было бы идеальным, особенно если вы планируете повторно использовать данные позже).