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

Ответ 1

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

Ответ 2

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

Ответ 3

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

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

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

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

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

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

Ответ 4

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

Ответ 5

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

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

Вы выполняете все элементы, подставляя каждую пару:

the absolute difference to the median, element value. 

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

Ответ 6

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

если порядок не имеет значения, выбор наименьшего k можно сделать в O (n) применим для k наименьшего значения к rhs медианы и 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 возвращает исходный список

Ответ 7

В списке чисел 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) состоит в том, чтобы начинать с я = 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].

Ответ 8

Четыре шага:

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

Ответ 9

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

Ответ 10

Если вы знаете индекс медианы, который должен быть просто 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 каждой стороны)

Ответ 11

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

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

Ответ 12

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