Поиск медианы несортированного массива

Ответ 1

Вы можете использовать алгоритм Median of Medians для поиска медианы несортированного массива в линейном времени.

Ответ 2

Я уже поддержал ответ @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 работает также, когда вы заранее не знаете количество элементов массива (если вам нужно решить ту же проблему для потока целых чисел, например, например). Более подробную информацию о том, как решить эту проблему, можно найти в следующей статье Медиана целочисленных потоков

Ответ 3

Quickselect работает в O (n), это также используется на этапе разделения Quicksort.

Ответ 4

Алгоритм быстрого выбора может найти 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)

Ответ 5

Это можно сделать с помощью алгоритма Quickselect в O (n), см. статистику K-го порядка (рандомизированные алгоритмы).

Ответ 6

Как говорит Википедия, медианная медиана теоретически 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).