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

Question

с учетом набора точек D и некоторого числа KI нужно найти все числа в 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) как массив типа dimple.

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

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

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