Ближайший номер к набору номеров

Question

Предположим, что у нас есть набор чисел как P = { p1, p2, p3, ..., pn } (длина (P) = n) и выберите число как q. Поэтому я хочу найти алгоритм для получения ближайшего члена набора P до q. Таким образом, вопрос заключается в следующем: какая структура подходит для хранения данных (p1, p2, ...) и алгоритмов поиска ближайшего члена от P к q в O(1) сложности времени.

Answer 1

1. Вы не можете получить O (1) сложность.Самое близкое к этому можно получить O (lg lg n), используя дерево Ван Эмда Боаса.
2. Если набор статический, используйте отсортированный вектор и двоичный поиск (O (lg n)), чтобы найтиближайший элемент.
3. Если набор может меняться между запросами, используйте соответствующую структуру данных для поддержки динамических наборов (например, AVL или красно-черное дерево).

Answer 2

Единственный способ получить O(1) сложность времени - это использовать O(pn) пробел и O(pn) время для предварительного упорядочения P и распределения значений в массиве pn.

Предзаказ P, поэтому p1 - это минимум, а pn - это максимум (я предполагаю, что они являются целыми числами.) Затем сохраните в массиве с размером (pn-p1+1) значения:

A(p1) = p1
for  i = 2  to  n
    for  q = p(i-1)+1  to  (p(i-1)+p(i))/2
        A(q) = p(i-1)
    for  q = (p(i-1)+p(i))/2  to  p(i) 
        A(q) = p(i)

Тогда все, что вам нужно проверить для определенного q, это:

if q < A(p1)
    closest = A(p1)
elif q > A(pn)
    closest = A(pn)
else
    closest = A(q)