Чтобы найти медиану несортированного массива, мы можем сделать min-кучу в O (nlogn) времени для n элементов, а затем мы можем извлечь один на один n/2 элемента для получения медианы. Но этот подход займет время O (nlogn).
Можем ли мы сделать то же самое с помощью некоторого метода в O (n) времени? Если мы можем, то, пожалуйста, скажите или предложите какой-нибудь метод.
Вы можете использовать алгоритм Median of Medians для поиска медианы несортированного массива в линейном времени.
Я уже поддержал ответ @dasblinkenlight, так как алгоритм Median of Medians фактически решает эту проблему в O (n) времени. Я хочу только добавить, что эта проблема может быть решена в O (n) раз, используя также кучи. Построение кучи может быть выполнено в O (n) раз, используя снизу вверх. Взгляните на следующую статью для подробного объяснения Куча сортировки
Предположим, что у вашего массива есть N элементов, вам нужно собрать две кучи: MaxHeap, содержащий первые N/2 элементы (или (N/2) +1, если N нечетно) и MinHeap, содержащий остальные элементы, Если N нечетно, то ваша медиана является максимальным элементом MaxHeap (O (1) путем получения max). Если N четно, то ваша медиана равна (MaxHeap.max() + MinHeap.min())/2, что также принимает O (1). Таким образом, реальная стоимость всей операции - операция построения кучи, которая равна O (n).
Кстати, этот алгоритм MaxHeap/MinHeap работает также, когда вы заранее не знаете количество элементов массива (если вам нужно решить ту же проблему для потока целых чисел, например, например). Более подробную информацию о том, как решить эту проблему, можно найти в следующей статье Медиана целочисленных потоков
Quickselect работает в O (n), это также используется на этапе разделения Quicksort.
Алгоритм быстрого выбора может найти k-й наименьший элемент массива в линейном (O(n)) времени выполнения. Вот реализация в python:
import random
def partition(L, v):
smaller = []
bigger = []
for val in L:
if val < v: smaller += [val]
if val > v: bigger += [val]
return (smaller, [v], bigger)
def top_k(L, k):
v = L[random.randrange(len(L))]
(left, middle, right) = partition(L, v)
# middle used below (in place of [v]) for clarity
if len(left) == k: return left
if len(left)+1 == k: return left + middle
if len(left) > k: return top_k(left, k)
return left + middle + top_k(right, k - len(left) - len(middle))
def median(L):
n = len(L)
l = top_k(L, n / 2 + 1)
return max(l)
Это можно сделать с помощью алгоритма Quickselect в O (n), см. статистику K-го порядка (рандомизированные алгоритмы).
Как говорит Википедия, медианная медиана теоретически o (N), но она не используется на практике, потому что накладные расходы на поиск "хороших" опорных точек делают ее слишком медленной. http://en.wikipedia.org/wiki/Selection_algorithm
Вот источник Java для алгоритма Quickselect для нахождения k-го элемента в массиве:
/**
* Returns position of k'th largest element of sub-list.
*
* @param list list to search, whose sub-list may be shuffled before
* returning
* @param lo first element of sub-list in list
* @param hi just after last element of sub-list in list
* @param k
* @return position of k'th largest element of (possibly shuffled) sub-list.
*/
static int select(double[] list, int lo, int hi, int k) {
int n = hi - lo;
if (n < 2)
return lo;
double pivot = list[lo + (k * 7919) % n]; // Pick a random pivot
// Triage list to [<pivot][=pivot][>pivot]
int nLess = 0, nSame = 0, nMore = 0;
int lo3 = lo;
int hi3 = hi;
while (lo3 < hi3) {
double e = list[lo3];
int cmp = compare(e, pivot);
if (cmp < 0) {
nLess++;
lo3++;
} else if (cmp > 0) {
swap(list, lo3, --hi3);
if (nSame > 0)
swap(list, hi3, hi3 + nSame);
nMore++;
} else {
nSame++;
swap(list, lo3, --hi3);
}
}
assert (nSame > 0);
assert (nLess + nSame + nMore == n);
assert (list[lo + nLess] == pivot);
assert (list[hi - nMore - 1] == pivot);
if (k >= n - nMore)
return select(list, hi - nMore, hi, k - nLess - nSame);
else if (k < nLess)
return select(list, lo, lo + nLess, k);
return lo + k;
}
Я не включил источник методов сравнения и свопинга, поэтому легко изменить код для работы с Object [] вместо double [].
На практике вы можете ожидать, что вышеуказанный код будет o (N).