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

Question

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

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

Проблема заключается в введении в Алгоритмы по Cormen, проблемы 9.3-7

Answer 1

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

Answer 2

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

Answer 3

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

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

Answer 4

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

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

После того как вы медиана от медианы медианы из-, держать ноту это значение.

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

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

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

Answer 5

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

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

from wikipedia

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) 

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

Answer 6

В списке чисел 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 7

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

Answer 8

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 9

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

Answer 10

Вы можете решить проблему так:.

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

Вы перебрать все элементы substutiting каждый с парой:

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

еще раз вы nth_element с п = к. после применения этого алгоритма вы гарантированно должны иметь k наименьших элементов в абсолютной разности сначала в новом массиве. Вы берете их индексы и СОВЕРШЕНО!