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

Question

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

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

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

Answer 1

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

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

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 с каждой стороны)