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

Question

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

Если медиана равна n, цифры слева меньше n, а цифры справа больше n. Однако массив не сортируется ни по левой, ни по правой стороне. Числа - это любой набор отдельных чисел, данных пользователем.

Проблема из «Введение в алгоритмы» по Кормену, проблема 9.3-7

Answer 1

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

Answer 2

Медиана медиан, вероятно, не сильно помогает в поиске ближайших соседей, по крайней мере, для больших 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) в целом.

Answer 3

med=Select(A,1,n,n/2)   //finds the median

for i=1 to n
   B[i]=mod(A[i]-med)

q=Select(B,1,n,k) //get the kth smallest difference

j=0
for i=1 to n
   if B[i]<=q 
     C[j]=A[i] //A[i], the real value should be assigned instead of B[i] which is only the difference between A[i] and median.
       j++
return C

Answer 4

Вы можете решить свою проблему следующим образом:

Вы можете найти медиану в O (n), w.g. используя алгоритм O (n) nth_element.

Вы перебираете все элементы, замещая каждый парой:

the absolute difference to the median, element's value. 

Еще раз вы делаете nth_element с n = k. после применения этого алгоритма вы гарантированно получите k самых маленьких элементов с абсолютной разницей первыми в новом массиве. Вы берете их индексы и СДЕЛАНО!

Answer 5

1. Найдите медиану в O (n). 2. создать новый массив, каждый элемент которого является абсолютным значением исходного значения, вычесть медиану 3. Найти k-е наименьшее число в O (n) 4. Желаемыми значениями являются элементы, абсолютная разница которых с медианой меньше или равно k-му наименьшему числу в новом массиве.

Answer 6

Четыре шага:

1. Сначала найдите медиану ( Медиана медианы ) - O (n)
2. Определить абсолютную разницу между медианой и каждым из элементов - O (n)
3. Используйте k-й алгоритм наименьшего элемента для получения результата ( Быстрый выбор ) - O (n)
4. Теперь нам нужно выбрать k, ближайший к массиву - O (n)

Answer 7

На самом деле ответ довольно прост. Все, что нам нужно сделать, это выбрать k элементов с наименьшими абсолютными отличиями от медианы, переходящей от m-1 к 0 и m + 1 к n-1, когда медиана находится в индексе m. Мы выбираем элементы, используя ту же идею, что и при объединении 2 отсортированных массивов.

Answer 8

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

Answer 9

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

Вы минимизируете выражение, которое получается из преобразования L в другой список, M, путем взятия разницы каждого элемента из медианы.

m=L[n/2]
M=abs(L-m)

i минимизирует M[n/2-k/2+i] + M[n/2+k/2+i].

Answer 10

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

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

из Википедии

 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 возвращает исходный список