Как найти все числа которые там расстояние от заданной точки меньше или равно целому n

Question

С учетом набора точек D и некоторого числа K I нужно найти все числа, находящиеся в D, такие, чтобы расстояние между K и любым найденным числом было меньше или равно целому числу N?

Пример: предположим, что у нас D={5,9,0,6,7} и K=8 и N=1, тогда результат должен быть {9,7}

Я думал об использовании дерева kd или дерева VP, но оба, как я понимаю (поправьте меня, если я ошибаюсь, пожалуйста), находят ближайших соседей и не заботятся о N в моем примере.

Answer 1

Подведем итог всем комментариям:

Решите эту проблему, поскольку грубая сила возьмет O(n) время итерации на каждый элемент в D и проверить, если его расстояние от k меньше чем n,

У вас большой набор данных, но много запросов, лучше выполнить предварительную обработку на D (с O(nlogn) и вы можете получить ответ в O(logn) -> сортируя D как предварительные процессы (в O(nlogn) как ямочка вроде массива.

Теперь по заданному запросу ищем k - обратите внимание, что двоичный поиск остановится, если число пропущено, но он остановится на ближайшем значении. С этого индекса начните распространение по обе стороны от D и для каждой проверки, если все еще в n спектр. Обратите внимание на распространение в разрешении, поскольку оно включает O(|output|),

В вашем примере: отсортировано D Уступать: [0,5,6,7,9], Попробуйте найти k=8 даст false, но индекс 3 или 4 (зависит от реализации). Пусть скажем, это индекс возврата 3. для 3 до последней проверки индекса, если arr[i] - k < n если так, то печатайте - если больше остановитесь. Для проверки другой стороны k - arr[i] < n - если так, напечатайте и если больше остановитесь -> это даст вам 7,9

Надеюсь, это поможет!