Znaleźć medianę nieposortowanej tablicy

Question

Aby znaleźć medianę nieposortowanej tablicy, możemy zrobić min-stapę w czasie O (nlogn) dla n elementów, a następnie możemy wyodrębnić jeden po drugim n/2 elementów, aby uzyskać mediana. Ale to podejście zajmie czas O (nlogn).

Czy możemy zrobić to samo według jakiejś metody w czasie O (n)? Jeśli możemy, to powiedz lub zasugeruj jakąś metodę.

Answer 1

Możesz użyć algorytmu Median of Medians, aby znaleźć medianę nieposortowanej tablicy w czasie liniowym.

Answer 2

Quickselect działa w O (n), jest to również używane w kroku podziału Quicksort.

Answer 3

Można to zrobić za pomocą funkcji Quickselect Algorithm w O (n), odnoszą się do statystyk porządku Kth (algorytmy randomizowane).

Answer 4

Algorytm szybkiego wyboru może znaleźć k-ty najmniejszy element tablicy w liniowym (O(n)) czasie działania. Oto implementacja w Pythonie:

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

Jak mówi wikipedia, Median-of-Medami teoretycznie jest O (n), ale to nie jest stosowany w praktyce, ponieważ narzut znalezienie „dobrych” czopy sprawia, że ​​zbyt wolno .
http://en.wikipedia.org/wiki/Selection_algorithm

Oto źródło Java algorytm Quickselect aby znaleźć element k'th w tablicy:

/** 
* 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; 
} 

Nie wliczone źródła z porównania i wymiennych metod, tak łatwo zmień kod do pracy z Object [] zamiast double [].

W praktyce można oczekiwać, że powyższy kod będzie o (N).

Answer 6

Już przegłosowałem odpowiedź @ dasblinkenlight, ponieważ algorytm Median of Medians rozwiązuje ten problem w czasie O (n). Chcę tylko dodać, że ten problem można rozwiązać w O (n) czasie, również za pomocą hałd. Budowanie sterty może być wykonane w czasie O (n) za pomocą oddolnego. Spójrz w następującym artykule o szczegółowe wyjaśnienie Heap sort

zakładając, że posiada elementy macierzy N, trzeba zbudować dwa stosy: A MaxHeap zawierający pierwsze N ​​/ 2 (lub elementy (N/2) +1 jeśli N jest nieparzyste) i MinHeap, która zawiera pozostałe elementy. Jeśli N jest nieparzyste, wówczas twoja mediana jest maksymalnym elementem MaxHeap (O (1) przez uzyskanie maksimum). Jeśli N jest parzyste, to twoja mediana to (MaxHeap.max() + MinHeap.min())/2 to również zajmuje O (1). Tak więc rzeczywistym kosztem całej operacji jest operacja budowania hałdy, która jest O (n).

Przy okazji ten algorytm MaxHeap/MinHeap działa również wtedy, gdy wcześniej nie znasz liczby elementów tablicy (jeśli musisz rozwiązać ten sam problem dla strumienia liczb całkowitych dla np.). Więcej informacji o tym, jak rozwiązać ten problem, można znaleźć w następującym artykule: Median Of integer streams