Как найти k ближайших соседей медианы n отличных чисел в O (n) временем?

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

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

Поскольку все элементы различны, может быть не более 2 элементов с одинаковым отличием от среднего. Я думаю, мне проще иметь 2 массива A [k] и B [k] - индекс, представляющий абсолютное значение разницы от среднего. Теперь задача состоит в том, чтобы просто заполнить массивы и выбрать k элементов, прочитав первые k непустых значений массивов, читающих A [i] и B [i] перед A [i + 1] и B [i + 1]. Это можно сделать за O (n) раз.

Если вы знаете индекс медианы, который должен быть просто ceil (array.length / 2), возможно, тогда это должен быть процесс перечисления n (xk), n ( х-к + 1), ..., п (х), п (х + 1), п (х + 2), ... п (х + к) где n - массив, x - индекс медианы, а k - количество необходимых вам соседей (возможно, k / 2, если вы хотите всего k, а не k с каждой стороны)

Вы уже знаете, как найти медиану в O (n)

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

из википедии

 function findFirstK(list, left, right, k)
 if right > left
     select pivotIndex between left and right
     pivotNewIndex := partition(list, left, right, pivotIndex)
     if pivotNewIndex > k  // new condition
         findFirstK(list, left, pivotNewIndex-1, k)
     if pivotNewIndex < k
         findFirstK(list, pivotNewIndex+1, right, k)

не забывайте особый случай, когда k == n возвращает исходный список

Вы можете использовать сортировку без сравнения, такую ​​как сортировка по основанию, в списке чисел L , а затем найти k ближайших соседей, рассматривая окна из k элементов и исследуют конечные точки окна. Другой способ сказать «найти окно» - найти i, который минимизирует abs (L [(nk) / 2 + i] - L [n / 2]) + abs (L [(n + k) / 2 + i] - L [n / 2]) (если k нечетное) или abs (L [(nk) / 2 + i] - L [n / 2]) + abs (L [(n + k) / 2 + i + 1] - L [n / 2]) (если k четное). Объединяя случаи, abs (L [(nk) / 2 + i] - L [n / 2]) + abs (L [(n + k) / 2 + i +! ​​(K & 1)] - L [n / 2]) . Простой способ поиска минимума O (k) - начать с i = 0, затем скользить влево или вправо, но вы должны быть в состоянии найти минимум в O (log (k)).

выражение, которое вы минимизируете, происходит от преобразования L в другой список,

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

Я бы просто рассматривал медианное значение как промежуточный результат, а ближайших соседей рассматривал бы как очередь с приоритетом. проблема ...

Как только у вас есть медиана из медианы-медиан, запишите ее значение.

Запустите алгоритм heapify для всех ваших данных - см. Wikipedia - Binary Heap . При сравнении основывайте результат на разнице относительно сохраненного медианного значения. Наивысший приоритет имеют элементы с самым низким ABS (значение - медиана). Это занимает O (n).

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

Пока k является константой, вы получаете O (n) медианы медиан, O (n) heapify и O (log n) извлечения, давая O ( n) в целом.