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

Question

Чтобы найти медиану несортированного массива, мы можем сделать min-кучу в O (nlogn) времени для n элементов, а затем мы можем извлечь по одному n/2 элементам, чтобы получить медиана. Но этот подход займет время O (nlogn).

Можем ли мы сделать то же с помощью некоторого метода в O (n) времени? Если мы сможем, то, пожалуйста, скажите или предложите какой-то метод.

Answer 1

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

Answer 2

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

Answer 3

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

Answer 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) 

Answer 5

Как говорит википедия, Медиана-оф-мидийцев теоретически O (N), но она не используется на практике, поскольку накладные расходы найти «хорошие» шарниров делает это слишком медленно ,
http://en.wikipedia.org/wiki/Selection_algorithm

Вот источник Java для алгоритма Быстрого выбора, чтобы найти элемент 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 [].

На практике вы можете ожидать, что приведенный выше код будет о (N).

Answer 6

Я уже поддержал ответ @dasblinkenlight, поскольку алгоритм Median of Medians фактически решает эту проблему в O (n) времени. Я хочу только добавить, что эта проблема может быть решена в O (n) раз, используя также кучи. Построение кучи может быть выполнено в O (n) раз, используя снизу вверх. Взгляните на следующую статью, чтобы получить подробное объяснение. Heap sort

Предположим, что ваш массив имеет N элементов, вам нужно собрать две кучи: MaxHeap, содержащий первые N/2 элементы (или (N/2) +1 если N нечетно) и MinHeap, содержащий остальные элементы. Если N нечетно, то ваша медиана является максимальным элементом MaxHeap (O (1) путем получения max). Если N четно, то ваша медиана равна (MaxHeap.max() + MinHeap.min())/2, что также принимает O (1). Таким образом, реальная стоимость всей операции - операция построения кучи, которая равна O (n).

BTW Этот алгоритм MaxHeap/MinHeap работает также, когда вы заранее не знаете количество элементов массива (если вам нужно решить ту же проблему для потока целых чисел, например, например). Более подробную информацию о том, как решить эту проблему, можно найти в следующей статье: Median Of integer streams