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

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

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

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

13.10.2009 00:36:34
Если медиана была в местоположении n, вы ищете значения в местоположении n + 1 и местоположении n-1?
Polaris878 13.10.2009 00:40:41
Являются ли числа числами или целыми числами с фиксированной запятой?
outis 13.10.2009 01:11:32
13 ОТВЕТОВ

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

-1
13.10.2009 00:44:50
Это не работает Медиана медианных алгоритмов НЕ сортирует элементы. Для этого потребуется O (n log n), в то время как медиана медианы работает на O (n).
Steve314 13.10.2009 01:07:33
Ах, извинения. Я прочитал оригинальный вопрос в версии 2, где он добавил, что он уже отсортировал его по порядку.
glasnt 13.10.2009 04:20:17

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

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

-1
13.10.2009 00:52:20
Хотя верно, что O (k) есть O (1), когда k постоянно, если k -> n, то это становится O (n ^ 2). Кроме того, как вы знаете, что k является константой? Если это так, то нельзя ли считать n постоянным?
Kirk Broadhurst 13.10.2009 00:54:58

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

9
13.10.2009 01:25:49
Разве не сложность heapify O (nlogn)?
Anonymous 13.10.2009 01:36:44
Если вы делаете это тупым способом (вставьте каждый элемент по очереди в изначально пустую кучу), то это O (n log n). Если вы используете алгоритм heapify, это O (n). См. Страницу википедии (раздел «Создание кучи») для более подробной информации.
Steve314 13.10.2009 01:49:31
Почему мы можем рассматривать k как константу? Что если k == n?
Yos 23.05.2017 12:21:13
@Yos - Во-первых, при определении сложности алгоритмов, если не указано иное, kпо общему правилу предполагается, что некоторая константа не зависит от n. Кроме того, в задаче по соглашению, известной как «k ближайших соседей», kвсегда представляет количество соседей, которые нужно найти, которое всегда постоянно (по крайней мере в том смысле, что оно не зависит от других, ограниченных общее количество вершин n). И это не случайно - существует гораздо более широкое соглашение, которое kпредставляет некоторую константу, независимую от других переменных.
Steve314 23.05.2017 21:27:55

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

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

0
13.10.2009 22:15:10

В списке чисел вы можете использовать несопоставимую сортировку, такую ​​как сортировка по осям 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].

0
13.10.2009 06:56:57

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

-1
13.10.2009 02:43:58
«выберите k элементов, прочитав первые k непустых значений массивов» - для этого необходимо отсортировать массивы. Сортировка этих массивов занимает время O (n log n).
Windows programmer 13.10.2009 05:42:08
@ Windows Programmer: только если вы делаете сортировку на основе сравнения.
outis 13.10.2009 06:57:55
РЕШЕНИЕ

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

0
14.10.2009 03:51:22
Но как мы выбираем их в O (n), учитывая, что элементы не отсортированы на основе их абсолютного отличия от медианы?
S..K 3.08.2011 10:38:00
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
4
12.10.2011 08:47:36
поскольку значения в массиве B могут быть равны, вы должны убедиться, что j не больше k. В то же время, если вы описываете свой ответ в тексте, другие могут понять вас лучше.
meteorgan 28.02.2012 02:46:28

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

19
9.05.2012 06:08:59
Вы должны взять модули чисел, прежде чем найти статистику k-го порядка, я думаю
iLoveCamelCase 6.09.2015 06:00:31

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

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

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

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

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

2
3.07.2013 15:15:14
Это так же, как ответ @ HalPri, который был опубликован за год до вашего.
John Kurlak 6.02.2014 04:16:23
Это лучше, чем ответ @ HalPri - @Shivendra использует absoulte difference, что решает проблему, которую я указал в своем комментарии к ответу @ HalPri
Zvika 10.12.2017 19:43:04

Четыре шага:

  1. Сначала найдите медиану ( медиану медианы ) - O (n)
  2. Определить абсолютную разницу между медианой и каждым из элементов - O (n)
  3. Используйте k-й алгоритм наименьшего элемента, чтобы получить результат ( Быстрый выбор ) - O (n)
  4. Теперь нам нужно выбрать k ближайший из массива - O (n)
1
13.08.2018 07:36:53
  1. Найдите медиану в O (n). 2. создать новый массив, каждый элемент которого является абсолютным значением исходного значения, вычесть медиану 3. Найти k-е наименьшее число в O (n) 4. Желаемыми значениями являются элементы, абсолютная разница которых с медианой меньше или равно k-е наименьшее число в новом массиве.
1
4.05.2019 20:31:44

Все ответы, предлагающие вычесть медиану из массива, дадут неверные результаты. Этот метод найдет элементы, наиболее близкие по значению, а не ближайшие по положению.

Например, если массив есть 1,2,3,4,5,10,20,30,40. Для k = 2 возвращаемое значение будет (3,4); что неверно. Правильный вывод должен быть (4,10), так как они ближайший сосед.

Правильный способ найти результат - использовать алгоритм выбора для поиска элементов верхней и нижней границ. Затем путем прямого сравнения найдите оставшиеся элементы из списка.

0
5.02.2020 23:16:11