Jak znaleźć medianę liczb w czasie liniowym za pomocą stosów?

Zobacz tę stronę Wikipedii na algorytmy wyboru . W szczególności przyjrzyj się algorytmowi bfprt i algorytmowi Mediana Medianów. Bfprt jest probabilistycznie liniowy, i jest wzorowany na quicksort; Mediana Medians jest gwarantowana liniowa, ale ma duży stały współczynnik i tak może trwać dłużej w praktyce, w zależności od wielkości zestawu danych.

Jeśli masz tylko kilkaset lub tysiące elementów, z których można wybrać medianę, podejrzewam, że prosty quicksort następnie bezpośrednie indeksowanie jest najłatwiejsze.

Są prawdopodobnie lepsze algorytmy, ale oto jak bym to zrobił:

Mają dwa wiadra i wartość. Wartość jest mediana, dwa wiadra są "większe niż mediana" i "mniejsze niż mediana". Dla każdego elementu x w tablicy, równoważenie kubełków jest takie, że big_bucket i small_bucket różnią się rozmiarem nie większym niż 1. Podczas przenoszenia przedmiotów z dużego wiadra do małego wiadra najpierw muszą przejść przez wartość średnią, aby się tam dostać (tzn. różnica 2 będzie pomyślnie przesuń element z jednego wiadra do następnego-różnica 1 spowoduje przesunięcie elementu z jednego wiadra do wartości Środkowej.) Na końcu pierwszego przejścia przez tablicę wartość powinna być twoją medianą.

Być może nie było tego w pobliżu, kiedy zadano pierwotne pytanie, ale teraz wiki ma link do źródła, a tutaj jest: http://ftp.cs.purdue.edu/research/technical_reports/1991/TR%2091-027.pdf

Konkretnie, Przejdź na stronę 17 i spójrz na opis RSEL4. Dowodzą one w twierdzeniu 3.2, że złożoność czasowa tego k-tego algorytmu doboru wynosi O (k). więc potrzeba O(n), aby zbudować stertę, i dodatkowe o(k), aby znaleźć k-ten najmniejszy element.

Its not really as prosto do przodu, jak sugerowały niektóre inne odpowiedzi

Jeśli wiesz więcej o strukturze danych sterty, łatwo zrozumiesz, że tak naprawdę jest. struktura sterty może być zbudowana w czasie O (n) , jest min sterta i Max sterta. element korzeniowy min heap da ci najmniejszy element. element główny sterty max daje element max. Po prostu budując stertę znajdujesz min i max. ten sam pomysł dla mediana i kth największy, podczas budowania sterty, można znaleźć mediana i kth największy patrząc na lewej lub prawej gałęzi drzewa i zachowując stałą ilość pamięci do przechowywania numeru elementu. itd.

Zapisz pierwszą liczbę całkowitą w tablicy i ustaw licznik na 1. Następnie Pętla przez pozostałe liczby całkowite w wektorze. Jeżeli bieżąca liczba całkowita w tablicy jest taka sama jak zapisana, licznik jest zwiększany o jeden, w przeciwnym razie licznik jest zmniejszany o jeden. Jeśli licznik kiedykolwiek osiągnie zero, wyrzuć zapisaną liczbę całkowitą i zastąp ją bieżącą liczbą całkowitą w tablicy. Kiedy w końcu przejrzysz wszystkie liczby całkowite, zostaje Ci jeden kandydat. Następnie musisz przejść przez tablica ponownie i policzyć wystąpienie kandydata, aby sprawdzić, czy to naprawdę jest dominator.

static int FindDominator(int[] arr)
{
int counter = 1;
int candidate = arr[0];
for(int i = 1; i < n; i++)
{
   if(arr[i] == candidate) counter++
    else 
   {
        counter--;
        if(counter == 0) { candidate = arr[i]; counter = 1; }
    }
}
counter = 0;
for(int i = 0;  i < n; i++)
{
    if(arr[i] == candidate) counter++;
}
if(counter > n / 2) return candidate;
else return -1;
}

Oczywiście min i max W O (n) są łatwe i nie wymagają sterty.

K ' - ty największy można zrobić dość prosto, utrzymując stertę wielkości k z najwyższych wartości k do tej pory. Runtime to O (n*logk). Można nazwać ten czas liniowy, jeśli k jest stałą wielkością i k

Myślę, że mediana nie jest jednak możliwa. Samo utworzenie sterty O(n) wymaga czasu O(N*logn).

Edit: Ok, po zastanowieniu się nad tym trochę więcej, IVlad ma rację. Możesz utworzyć stertę w O (n), dla ustalonego rozmiaru. Ale... to nie pomaga operacji z jego medianą. Technika tworzenia sterty liniowej wytwarza tylko poprawną stertę jako jej końcowy wynik. Proste podejście do robienia N wstawek, skutkujące poprawną stertą po każdym kroku to O(n * logn).

Wydaje mi się, że użycie sterty do znalezienia mediany wymagałoby użycia tych uruchomionych pod-sterty. Na przykład, była tu zamieszczona odpowiedź (która wydaje się być teraz usunięta), która łączyła się z postem na blogu sugerującym algorytm dla tego problemu. Śledził biegową medianę za pomocą dwóch stosów (mniejsza połowa i większa połowa), ponieważ wykonuje pojedyncze przejście przez dane. Wymagałoby to wolniejszego, naiwnego podejścia do sterty, ponieważ polega ono na utrzymywaniu poprawnych Stert podczas wstawiania i usuwania z nich.

Czy Jest jakiś inny sposób, aby znaleźć medianę przy użyciu techniki liniowego tworzenia sterty jednego strzału?