Jak znaleźć k-ty największy element w nieposortowanej tablicy o długości nw O (n)?

220

Uważam, że istnieje sposób na znalezienie k-tego największego elementu w nieposortowanej tablicy o długości n w O (n). A może to „oczekiwane” O (n) lub coś takiego. Jak możemy to zrobić?

MrDatabase
źródło
49
Nawiasem mówiąc, prawie każdy opisany tutaj algorytm zmienia się w O (n ^ 2) lub O (n log n), gdy k == n. Oznacza to, że nie sądzę, aby jeden z nich miał wartość O (n) dla wszystkich wartości k. Zostałem zmodowany za wskazanie tego, ale pomyślałem, że powinieneś wiedzieć.
Kirk Strauser
19
Algorytmami wyboru może być O (n) dla dowolnej stałej wartości k. Oznacza to, że możesz mieć algorytm wyboru dla k = 25, który jest O (n) dla dowolnej wartości n, i możesz to zrobić dla dowolnej określonej wartości k, która nie jest związana z n. Przypadek, w którym algorytm nie jest już O (n), ma miejsce, gdy wartość k ma pewną zależność od wartości n, na przykład k = n lub k = n / 2. Nie oznacza to jednak, że jeśli zdarzy się, że uruchomisz algorytm k = 25 na liście 25 pozycji, nagle przestanie być on O (n), ponieważ notacja O opisuje właściwość algorytmu, a nie konkretny uruchomić.
Tyler McHenry
1
Zadano mi to pytanie w wywiadzie z Amazonem jako ogólny przypadek znalezienia drugiego co do wielkości elementu. Przy okazji, kiedy prowadzący wywiad przeprowadził wywiad, nie zapytałem, czy mogę zniszczyć pierwotną tablicę (tj. Posortować ją), więc wpadłem na skomplikowane rozwiązanie.
Sambatyon
4
To jest pytanie 9 w kolumnie 11 (Sortowanie) pereł programistycznych autorstwa Jona Bentleya.
Qiang Xu,
3
@KirkStrauser: Jeśli k == n lub k == n-1, staje się to trywialne. Możemy uzyskać maksimum lub drugie maksimum w pojedynczym przejściu. Dlatego podane tutaj algorytmy będą praktycznie stosowane dla wartości k, które nie należą do {1,2, n-1, n}
Aditya Joshee

Odpowiedzi:

173

Nazywa się to znajdowaniem statystyki k-tego rzędu . Istnieje bardzo prosty algorytm randomizowany (zwany szybkim wyborem ), który zajmuje O(n)średni czas, O(n^2)najgorszy przypadek, oraz dość skomplikowany algorytm nielosowy (zwany introseleksem ), który zajmuje O(n)najgorszy czas. Jest trochę informacji na Wikipedii , ale to nie jest zbyt dobre.

Wszystko, czego potrzebujesz, znajduje się w tych slajdach PowerPoint . Aby wyodrębnić podstawowy algorytm algorytmu O(n)najgorszego przypadku (introselect):

Select(A,n,i):
    Divide input into ⌈n/5⌉ groups of size 5.

    /* Partition on median-of-medians */
    medians = array of each group’s median.
    pivot = Select(medians, ⌈n/5⌉, ⌈n/10⌉)
    Left Array L and Right Array G = partition(A, pivot)

    /* Find ith element in L, pivot, or G */
    k = |L| + 1
    If i = k, return pivot
    If i < k, return Select(L, k-1, i)
    If i > k, return Select(G, n-k, i-k)

Jest to również bardzo ładnie wyszczególnione w książce Wprowadzenie do algorytmów autorstwa Cormen i in.

eladv
źródło
6
Dziękuję za slajdy.
Kshitij Banerjee
5
Dlaczego musi działać w rozmiarze 5? Dlaczego nie działa z rozmiarem 3?
Joffrey Baratheon
11
@eladv Link do slajdów jest zerwany :(
Misha Moroshko
7
@eladv Plese naprawić zepsuty link.
maxx777
1
@MishaMoroshko link został naprawiony
alfasin
118

Jeśli chcesz prawdziwego O(n)algorytmu, w przeciwieństwie do O(kn)czegoś podobnego, powinieneś użyć szybkiego wyboru (jest to po prostu szybki sort, w którym wyrzucasz partycję, która Cię nie interesuje). Mój prof ma świetny opis, z analizą środowiska wykonawczego: ( odniesienie )

Algorytm QuickSelect szybko znajduje k-ty najmniejszy element nieposortowanej tablicy nelementów. Jest to algorytm Randomized , więc obliczamy najgorszy spodziewany czas działania.

Oto algorytm.

QuickSelect(A, k)
  let r be chosen uniformly at random in the range 1 to length(A)
  let pivot = A[r]
  let A1, A2 be new arrays
  # split into a pile A1 of small elements and A2 of big elements
  for i = 1 to n
    if A[i] < pivot then
      append A[i] to A1
    else if A[i] > pivot then
      append A[i] to A2
    else
      # do nothing
  end for
  if k <= length(A1):
    # it's in the pile of small elements
    return QuickSelect(A1, k)
  else if k > length(A) - length(A2)
    # it's in the pile of big elements
    return QuickSelect(A2, k - (length(A) - length(A2))
  else
    # it's equal to the pivot
    return pivot

Jaki jest czas działania tego algorytmu? Jeśli przeciwnik rzuci za nas monety, może się okazać, że oś jest zawsze największym elementem i kwynosi zawsze 1, co daje czas działania

T(n) = Theta(n) + T(n-1) = Theta(n2)

Ale jeśli wybory są rzeczywiście losowe, oczekiwany czas działania jest podawany przez

T(n) <= Theta(n) + (1/n) ∑i=1 to nT(max(i, n-i-1))

gdzie przyjmujemy niezupełnie uzasadnione założenie, że rekurencja zawsze wyląduje w większym A1lub A2.

Zgadnijmy T(n) <= andla niektórych a. Potem dostaniemy

T(n) 
 <= cn + (1/n) ∑i=1 to nT(max(i-1, n-i))
 = cn + (1/n) ∑i=1 to floor(n/2) T(n-i) + (1/n) ∑i=floor(n/2)+1 to n T(i)
 <= cn + 2 (1/n) ∑i=floor(n/2) to n T(i)
 <= cn + 2 (1/n) ∑i=floor(n/2) to n ai

a teraz musimy jakoś zdobyć horrendalną sumę po prawej stronie znaku plus, aby pochłonąć cnlewą. Jeśli po prostu to związamy , otrzymamy z grubsza . Ale to jest za duże - nie ma miejsca na wyciskanie w dodatku . Rozwińmy więc sumę za pomocą wzoru szeregu arytmetycznego:2(1/n) ∑i=n/2 to n an2(1/n)(n/2)an = ancn

i=floor(n/2) to n i  
 = ∑i=1 to n i - ∑i=1 to floor(n/2) i  
 = n(n+1)/2 - floor(n/2)(floor(n/2)+1)/2  
 <= n2/2 - (n/4)2/2  
 = (15/32)n2

gdzie korzystamy z tego, że n jest „wystarczająco duży”, aby zastąpić brzydkie floor(n/2)czynniki znacznie czystszym (i mniejszym) n/4. Teraz możemy kontynuować

cn + 2 (1/n) ∑i=floor(n/2) to n ai,
 <= cn + (2a/n) (15/32) n2
 = n (c + (15/16)a)
 <= an

pod warunkiem a > 16c.

To daje T(n) = O(n). To jasne Omega(n), więc rozumiemy T(n) = Theta(n).

Ying Xiao
źródło
12
Szybki wybór to tylko O ​​(n) w przeciętnym przypadku. Algorytm mediany mediany może być zastosowany do rozwiązania problemu w czasie O (n) w najgorszym przypadku.
John Kurlak,
Co to znaczy k > length(A) - length(A2)?
WoooHaaaa
to nie O (n), ponownie wywołujesz funkcję jako rekurencyjną, T (n). W funkcji rekurencyjnej T (n) znajduje się już O (n), więc oczywiście bez zastanowienia ogólna złożoność byłaby większa niż O (n).
user1735921,
3
@MrROY Zważywszy, że mamy podzielony Ana A1i A2wokół przegubu, wiemy, że length(A) == length(A1)+length(A2)+1. Jest więc k > length(A)-length(A2)równoważne k > length(A1)+1, co jest prawdą, gdy kjest gdzieś w środku A2.
Filipe Gonçalves,
@ FilipeGonçalves, tak, jeśli nie ma zduplikowanych elementów w osi przestawnej. Len (A1) + Len (A2) + K-duplikat =
Len
16

Szybkie Google na ten temat („k-ty największy zestaw elementów”) zwrócił to: http://discuss.joelonsoftware.com/default.asp?interview.11.509587.17

"Make one pass through tracking the three largest values so far." 

(to było specjalnie dla największych 3D)

i ta odpowiedź:

Build a heap/priority queue.  O(n)
Pop top element.  O(log n)
Pop top element.  O(log n)
Pop top element.  O(log n)

Total = O(n) + 3 O(log n) = O(n)
królikarnia
źródło
15
cóż, to faktycznie O (n) + O (k log n), które nie zmniejszają się dla znaczących wartości K
Jimmy
2
Ale znalezienie punktu wstawienia na tej podwójnie połączonej liście to O (k).
Kirk Strauser
1
A jeśli k jest ustalone, O (k) = O (1)
Tyler McHenry
1
@warren: Big-O jest przybliżone, ale zawsze przesadzasz. Na przykład Quicksort to O (n ^ 2), ponieważ jest to najgorszy przypadek. tym jest O (n + k log n).
Claudiu
1
nie można traktować wartości k jako stałej. Możliwe jest, że k = n, w którym to przypadku złożoność czasu wynosi O (
nlogn
11

Lubisz quicksort. Wybierz element losowo i wepchnij wszystko wyżej lub niżej. W tym momencie będziesz wiedział, który element faktycznie wybrałeś, a jeśli jest to k-ty element, który zrobiłeś, w przeciwnym razie powtórzysz z binem (wyższym lub niższym), do którego wpadłby k-ty element. Mówiąc statystycznie, czas trzeba znaleźć, aby kth element wyrósł z n, O (n).

śmierdzący
źródło
2
Właśnie tym jest szybki wybór, FWIW.
rogerdpack,
6

Companion Programisty do algorytm analizy daje wersję, która jest O (n), chociaż Autor stwierdza, że stały czynnik jest tak wysoka, że pewnie wolą naiwny sortowania-the-listy-then-wybierz metodę.

Odpowiedziałem na twoje pytanie :)

Jimmy
źródło
2
Nie do końca prawda we wszystkich przypadkach. Wdrożyłem medianę median i porównałem ją z wbudowaną metodą sortowania w .NET, a niestandardowe rozwiązanie naprawdę działało szybciej o rząd wielkości. Teraz prawdziwe pytanie brzmi: czy ma to dla ciebie znaczenie w danych okolicznościach. Pisanie i debugowanie 100 wierszy kodu w porównaniu do jednej linijki jest opłacalne tylko wtedy, gdy kod ten będzie wykonywany tyle razy, że użytkownik zacznie zauważać różnicę w czasie wykonywania i poczuje dyskomfort czekający na zakończenie operacji.
Zoran Horvat,
5

Standardowa biblioteka C ++ ma prawie dokładnie to wywołanie funkcjinth_element , chociaż modyfikuje dane. Oczekiwał liniowego czasu działania, O (N), a także dokonuje częściowego sortowania.

const int N = ...;
double a[N];
// ... 
const int m = ...; // m < N
nth_element (a, a + m, a + N);
// a[m] contains the mth element in a
David Nehme
źródło
1
Nie, ma oczekiwany średni czas działania O (n). Na przykład quicksort to średnio O (nlogn) z najgorszym przypadkiem O (n ^ 2). Wow, coś wprost nie tak!
Kirk Strauser
5
Nie, w tej odpowiedzi nie ma nic złego. Działa, a standard C ++ wymaga oczekiwanego liniowego czasu działania.
David Nehme
Zostałem poproszony w wywiadzie, aby założyć dostępność przestrzeni O (k), a „n” jest bardzo duże. Nie mogłem mu powiedzieć O (n), ponieważ myślałem, że nth_element będzie potrzebował miejsca o (n). Czy się mylę? Czy podstawowy algorytm nie jest oparty na QuickSort dla nth_element?
Manish Baphna,
4

Chociaż nie jestem bardzo pewny co do złożoności O (n), ale na pewno będzie między O (n) a nLog (n). Upewnij się także, że jesteś bliżej O (n) niż nLog (n). Funkcja jest napisana w Javie

public int quickSelect(ArrayList<Integer>list, int nthSmallest){
    //Choose random number in range of 0 to array length
    Random random =  new Random();
    //This will give random number which is not greater than length - 1
    int pivotIndex = random.nextInt(list.size() - 1); 

    int pivot = list.get(pivotIndex);

    ArrayList<Integer> smallerNumberList = new ArrayList<Integer>();
    ArrayList<Integer> greaterNumberList = new ArrayList<Integer>();

    //Split list into two. 
    //Value smaller than pivot should go to smallerNumberList
    //Value greater than pivot should go to greaterNumberList
    //Do nothing for value which is equal to pivot
    for(int i=0; i<list.size(); i++){
        if(list.get(i)<pivot){
            smallerNumberList.add(list.get(i));
        }
        else if(list.get(i)>pivot){
            greaterNumberList.add(list.get(i));
        }
        else{
            //Do nothing
        }
    }

    //If smallerNumberList size is greater than nthSmallest value, nthSmallest number must be in this list 
    if(nthSmallest < smallerNumberList.size()){
        return quickSelect(smallerNumberList, nthSmallest);
    }
    //If nthSmallest is greater than [ list.size() - greaterNumberList.size() ], nthSmallest number must be in this list
    //The step is bit tricky. If confusing, please see the above loop once again for clarification.
    else if(nthSmallest > (list.size() - greaterNumberList.size())){
        //nthSmallest will have to be changed here. [ list.size() - greaterNumberList.size() ] elements are already in 
        //smallerNumberList
        nthSmallest = nthSmallest - (list.size() - greaterNumberList.size());
        return quickSelect(greaterNumberList,nthSmallest);
    }
    else{
        return pivot;
    }
}
prithvi zankat
źródło
Ładne kodowanie, +1. Ale nie ma potrzeby używania dodatkowej przestrzeni.
Hengameh
4

Zaimplementowałem znalezienie kth minimum w n nieposortowanych elementach za pomocą programowania dynamicznego, a konkretnie metody turniejowej. Czas wykonania wynosi O (n + klog (n)). Zastosowany mechanizm jest wymieniony jako jedna z metod na stronie Wikipedii dotyczących algorytmu selekcji (jak wskazano w jednym z powyższych postów). Możesz przeczytać o algorytmie, a także znaleźć kod (java) na mojej stronie blogu Finding Kth Minimum . Dodatkowo logika może dokonywać częściowego uporządkowania listy - zwraca pierwszy K min (lub max) w czasie O (klog (n)).

Mimo że kod podał wynik k-tego minimum, można zastosować podobną logikę, aby znaleźć k-tego maksimum w O (klog (n)), ignorując wstępne prace wykonane w celu utworzenia drzewa turniejowego.

Malkit S. Bhasin
źródło
3

Możesz to zrobić w O (n + kn) = O (n) (dla stałej k) dla czasu i O (k) dla przestrzeni, śledząc k największych elementów, które widziałeś.

Dla każdego elementu w tablicy możesz zeskanować listę k największych i zastąpić najmniejszy element nowym, jeśli jest większy.

Priorytetowe rozwiązanie sterty Warrena jest jednak fajniejsze.

Rob Walker
źródło
3
Byłby to najgorszy przypadek O (n ^ 2), w którym prosi się o najmniejszy przedmiot.
Elie
2
„Najmniejszy element” oznacza, że ​​k = n, więc k nie jest już stałe.
Tyler McHenry,
A może trzymaj stertę (lub stertę odwróconą lub zrównoważone drzewo) największego k, jaki do tej pory widziałeś O(n log k)... nadal degeneruje się do O (nlogn) w przypadku dużego k. Myślałam, że będzie działać dobrze dla małych wartości k jednakże ... być może szybciej niż niektóre inne algorytmy wymienione tutaj [???]
rogerdpack
3

Seksowny szybki wybór w Pythonie

def quickselect(arr, k):
    '''
     k = 1 returns first element in ascending order.
     can be easily modified to return first element in descending order
    '''

    r = random.randrange(0, len(arr))

    a1 = [i for i in arr if i < arr[r]] '''partition'''
    a2 = [i for i in arr if i > arr[r]]

    if k <= len(a1):
        return quickselect(a1, k)
    elif k > len(arr)-len(a2):
        return quickselect(a2, k - (len(arr) - len(a2)))
    else:
        return arr[r]
hoder
źródło
Dobre rozwiązanie, z tym wyjątkiem, że zwraca k-ty najmniejszy element z nieposortowanej listy. Odwrócenie operatorów porównania w wyrażeniach listy a1 = [i for i in arr if i > arr[r]]i a2 = [i for i in arr if i < arr[r]]zwróci k-ty największy element.
gumption
Od małego testu porównawczego, nawet na dużych tablicach, sortowanie (z listami numpy.sortfor numpy arraylub sortedfor) jest szybsze niż użycie tej ręcznej implementacji.
Næreen
2

Znajdź medianę tablicy w czasie liniowym, a następnie użyj procedury podziału dokładnie tak, jak w szybkim sortowaniu, aby podzielić tablicę na dwie części, wartości na lewo od mediany mniejsze (<) niż niż mediana i na prawo większe niż (>) mediana , to też można zrobić w czasie liniowym, teraz przejdź do tej części tablicy, w której znajduje się kth element, Teraz rekurencja staje się: T (n) = T (n / 2) + cn, co daje mi O (n) overal.

pranjal
źródło
Nie ma potrzeby szukania mediany. bez mediany twoje podejście jest nadal w porządku.
Hengameh
2
A jak znaleźć medianę w czasie liniowym, czy odważę się zapytać? ... :)
rogerdpack,
2

Poniżej znajduje się link do pełnej implementacji z dość obszernym wyjaśnieniem, jak działa algorytm znajdowania elementu Kth w niesortowanym algorytmie. Podstawową ideą jest podzielenie tablicy na partycje jak w QuickSort. Aby jednak uniknąć ekstremalnych przypadków (np. Gdy na każdym kroku wybierany jest najmniejszy element, tak że algorytm ulega degeneracji do czasu działania O (n ^ 2)), stosuje się specjalny wybór przestawny, zwany algorytmem mediany median. Całe rozwiązanie działa w czasie O (n) w najgorszym i przeciętnym przypadku.

Oto link do pełnego artykułu (chodzi o znalezienie Kth najmniejszego elementu, ale zasada jest taka sama w przypadku znalezienia Kth największego ):

Znajdowanie K-tego najmniejszego elementu w niesortowanej tablicy

Zoran Horvat
źródło
2

Zgodnie z tym artykułem Znalezienie K-tej największej pozycji na liście n pozycji,O(n) w najgorszym przypadku potrzebny będzie następujący algorytm .

  1. Podziel tablicę na n / 5 list po 5 elementów każdy.
  2. Znajdź medianę w każdej podrzędnej tablicy 5 elementów.
  3. Rekurencyjnie znajdź medianę wszystkich median, nazwijmy to M
  4. Podziel tablicę na dwie podgrupy 1. podgrupa zawiera elementy większe niż M, powiedzmy, że ta podgrupa ma wartość a1, podczas gdy inna pod-tablica zawiera elementy mniejsze niż M., nazwijmy tę pod-tablicę a2.
  5. Jeśli k <= | a1 |, zwróć wybór (a1, k).
  6. Jeśli k− 1 = | a1 |, zwróć M.
  7. Jeśli k> | a1 | + 1, zwraca wybór (a2, k −a1 - 1).

Analiza: zgodnie z sugestią w oryginalnym artykule:

Używamy mediany, aby podzielić listę na dwie połowy (pierwsza połowa, jeśli k <= n/2, a druga połowa w przeciwnym razie). Algorytm ten wymaga czasu cnna pierwszym poziomie rekurencji dla pewnej stałej c, cn/2na następnym poziomie (ponieważ powtarzamy się na liście o rozmiarze n / 2), cn/4na trzecim poziomie i tak dalej. Całkowity czas to cn + cn/2 + cn/4 + .... = 2cn = o(n).

Dlaczego rozmiar partycji jest brany 5, a nie 3?

Jak wspomniano w oryginalnym artykule :

Dzielenie listy przez 5 zapewnia najgorszy przypadek podziału 70–30. Przynajmniej połowa median większa niż mediana median, stąd co najmniej połowa n / 5 bloków ma co najmniej 3 elementy, co daje 3n/10podział, który oznacza, że ​​druga partycja to 7n / 10 w najgorszym przypadku. To daje T(n) = T(n/5)+T(7n/10)+O(n). Since n/5+7n/10 < 1najgorszy możliwy czas działania O(n).

Teraz próbowałem zaimplementować powyższy algorytm jako:

public static int findKthLargestUsingMedian(Integer[] array, int k) {
        // Step 1: Divide the list into n/5 lists of 5 element each.
        int noOfRequiredLists = (int) Math.ceil(array.length / 5.0);
        // Step 2: Find pivotal element aka median of medians.
        int medianOfMedian =  findMedianOfMedians(array, noOfRequiredLists);
        //Now we need two lists split using medianOfMedian as pivot. All elements in list listOne will be grater than medianOfMedian and listTwo will have elements lesser than medianOfMedian.
        List<Integer> listWithGreaterNumbers = new ArrayList<>(); // elements greater than medianOfMedian
        List<Integer> listWithSmallerNumbers = new ArrayList<>(); // elements less than medianOfMedian
        for (Integer element : array) {
            if (element < medianOfMedian) {
                listWithSmallerNumbers.add(element);
            } else if (element > medianOfMedian) {
                listWithGreaterNumbers.add(element);
            }
        }
        // Next step.
        if (k <= listWithGreaterNumbers.size()) return findKthLargestUsingMedian((Integer[]) listWithGreaterNumbers.toArray(new Integer[listWithGreaterNumbers.size()]), k);
        else if ((k - 1) == listWithGreaterNumbers.size()) return medianOfMedian;
        else if (k > (listWithGreaterNumbers.size() + 1)) return findKthLargestUsingMedian((Integer[]) listWithSmallerNumbers.toArray(new Integer[listWithSmallerNumbers.size()]), k-listWithGreaterNumbers.size()-1);
        return -1;
    }

    public static int findMedianOfMedians(Integer[] mainList, int noOfRequiredLists) {
        int[] medians = new int[noOfRequiredLists];
        for (int count = 0; count < noOfRequiredLists; count++) {
            int startOfPartialArray = 5 * count;
            int endOfPartialArray = startOfPartialArray + 5;
            Integer[] partialArray = Arrays.copyOfRange((Integer[]) mainList, startOfPartialArray, endOfPartialArray);
            // Step 2: Find median of each of these sublists.
            int medianIndex = partialArray.length/2;
            medians[count] = partialArray[medianIndex];
        }
        // Step 3: Find median of the medians.
        return medians[medians.length / 2];
    }

Dla uproszczenia inny algorytm korzysta z kolejki priorytetowej i zajmuje dużo czasu O(nlogn).

public static int findKthLargestUsingPriorityQueue(Integer[] nums, int k) {
        int p = 0;
        int numElements = nums.length;
        // create priority queue where all the elements of nums will be stored
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();

        // place all the elements of the array to this priority queue
        for (int n : nums) {
            pq.add(n);
        }

        // extract the kth largest element
        while (numElements - k + 1 > 0) {
            p = pq.poll();
            k++;
        }

        return p;
    }

Oba te algorytmy można przetestować jako:

public static void main(String[] args) throws IOException {
        Integer[] numbers = new Integer[]{2, 3, 5, 4, 1, 12, 11, 13, 16, 7, 8, 6, 10, 9, 17, 15, 19, 20, 18, 23, 21, 22, 25, 24, 14};
        System.out.println(findKthLargestUsingMedian(numbers, 8));
        System.out.println(findKthLargestUsingPriorityQueue(numbers, 8));
    }

Zgodnie z oczekiwaniami dane wyjściowe to: 18 18

akhil_mittal
źródło
@rogerdpack Podałem link, którego użyłem.
akhil_mittal
2

Co powiesz na to podejście?

Zachowaj a buffer of length ki a tmp_max, otrzymywanie tmp_max to O (k) i jest wykonywane n razy, więc coś w styluO(kn)

wprowadź opis zdjęcia tutaj

Czy to prawda, czy coś mi brakuje?

Mimo, że nie jest to średni przypadek szybkiego wyboru i najgorszy przypadek mediany statystyki, to jest dość łatwy do zrozumienia i wdrożenia.

Aishwat Singh
źródło
1
Lubię to, łatwiej zrozumieć. Chociaż złożoność to O (nk), jak zauważyłeś.
Hajjat,
1

iteruj po liście. jeśli bieżąca wartość jest większa niż zapisana największa wartość, zapisz ją jako największą wartość i podbij 1-4 w dół, a 5 spadnie z listy. Jeśli nie, porównaj go z numerem 2 i zrób to samo. Powtórz, sprawdzając względem wszystkich 5 zapisanych wartości. powinno to zrobić w O (n)

Kevin
źródło
Ten „wypukłość” to O (n), jeśli używasz tablicy, lub w dół do O (log n) (myślę), jeśli używasz lepszej struktury.
Kirk Strauser
To nie musi być O (log k) - jeśli lista jest powiązana lista następnie dodanie nowego elementu do góry i spada ostatni element jest bardziej jak O (2)
Alnitak
Wypadek wynosiłby O (k) dla listy opartej na tablicy, O (1) dla odpowiednio połączonej listy. Tak czy inaczej, tego rodzaju pytanie ogólnie zakłada, że ​​będzie miało minimalny wpływ w porównaniu do n i nie wprowadza już żadnych czynników n.
bobince
byłoby również O (1), jeśli guz użyje bufora pierścieniowego
Alnitak
1
W każdym razie algorytm komentarza jest niekompletny, nie bierze pod uwagę elementu n, który jest nowy (np.) Drugi co do wielkości. Najgorsze zachowanie, w którym każdy element in musi być porównywany z każdym elementem w tabeli najlepszych wyników, to O (kn) - ale to prawdopodobnie oznacza O (n) pod względem pytania.
bobince
1

chciałbym zasugerować jedną odpowiedź

jeśli weźmiemy pierwsze k elementów i posortujemy je w połączoną listę wartości k

teraz dla każdej innej wartości, nawet w najgorszym przypadku, jeśli wykonujemy sortowanie wstawiania dla pozostałych wartości nk, nawet w najgorszym przypadku liczba porównań będzie k * (nk), a dla poprzednich sortowanych wartości k niech będzie to k * (k- 1) więc wychodzi na to, że jest (nk-k), co oznacza o (n)

Twoje zdrowie


źródło
1
sortowanie zajmuje czas nlogn ... algorytm powinien działać w czasie liniowym
MrDatabase
1

Wyjaśnienie algorytmu median of of medians w celu znalezienia k-tej największej liczby całkowitej spośród n można znaleźć tutaj: http://cs.indstate.edu/~spitla/presentation.pdf

Implementacja w c ++ jest poniżej:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int findMedian(vector<int> vec){
//    Find median of a vector
    int median;
    size_t size = vec.size();
    median = vec[(size/2)];
    return median;
}

int findMedianOfMedians(vector<vector<int> > values){
    vector<int> medians;

    for (int i = 0; i < values.size(); i++) {
        int m = findMedian(values[i]);
        medians.push_back(m);
    }

    return findMedian(medians);
}

void selectionByMedianOfMedians(const vector<int> values, int k){
//    Divide the list into n/5 lists of 5 elements each
    vector<vector<int> > vec2D;

    int count = 0;
    while (count != values.size()) {
        int countRow = 0;
        vector<int> row;

        while ((countRow < 5) && (count < values.size())) {
            row.push_back(values[count]);
            count++;
            countRow++;
        }
        vec2D.push_back(row);
    }

    cout<<endl<<endl<<"Printing 2D vector : "<<endl;
    for (int i = 0; i < vec2D.size(); i++) {
        for (int j = 0; j < vec2D[i].size(); j++) {
            cout<<vec2D[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<endl;

//    Calculating a new pivot for making splits
    int m = findMedianOfMedians(vec2D);
    cout<<"Median of medians is : "<<m<<endl;

//    Partition the list into unique elements larger than 'm' (call this sublist L1) and
//    those smaller them 'm' (call this sublist L2)
    vector<int> L1, L2;

    for (int i = 0; i < vec2D.size(); i++) {
        for (int j = 0; j < vec2D[i].size(); j++) {
            if (vec2D[i][j] > m) {
                L1.push_back(vec2D[i][j]);
            }else if (vec2D[i][j] < m){
                L2.push_back(vec2D[i][j]);
            }
        }
    }

//    Checking the splits as per the new pivot 'm'
    cout<<endl<<"Printing L1 : "<<endl;
    for (int i = 0; i < L1.size(); i++) {
        cout<<L1[i]<<" ";
    }

    cout<<endl<<endl<<"Printing L2 : "<<endl;
    for (int i = 0; i < L2.size(); i++) {
        cout<<L2[i]<<" ";
    }

//    Recursive calls
    if ((k - 1) == L1.size()) {
        cout<<endl<<endl<<"Answer :"<<m;
    }else if (k <= L1.size()) {
        return selectionByMedianOfMedians(L1, k);
    }else if (k > (L1.size() + 1)){
        return selectionByMedianOfMedians(L2, k-((int)L1.size())-1);
    }

}

int main()
{
    int values[] = {2, 3, 5, 4, 1, 12, 11, 13, 16, 7, 8, 6, 10, 9, 17, 15, 19, 20, 18, 23, 21, 22, 25, 24, 14};

    vector<int> vec(values, values + 25);

    cout<<"The given array is : "<<endl;
    for (int i = 0; i < vec.size(); i++) {
        cout<<vec[i]<<" ";
    }

    selectionByMedianOfMedians(vec, 8);

    return 0;
}
totjammykd
źródło
To rozwiązanie nie działa. Trzeba posortować tablicę przed zwróceniem mediany dla przypadku 5-elementowego.
Agnishom Chattopadhyay
1

Istnieje również algorytm wyboru Wirtha , który ma prostszą implementację niż QuickSelect. Algorytm wyboru Wirtha jest wolniejszy niż QuickSelect, ale z pewnymi ulepszeniami staje się szybszy.

Bardziej szczegółowo. Korzystając z optymalizacji MODIFIND Vladimira Zabrodsky'ego i wyboru środkowej z 3 osi obrotu oraz zwracając uwagę na końcowe kroki partycjonowania części algorytmu, opracowałem następujący algorytm (prawdopodobnie o nazwie „LefSelect”):

#define F_SWAP(a,b) { float temp=(a);(a)=(b);(b)=temp; }

# Note: The code needs more than 2 elements to work
float lefselect(float a[], const int n, const int k) {
    int l=0, m = n-1, i=l, j=m;
    float x;

    while (l<m) {
        if( a[k] < a[i] ) F_SWAP(a[i],a[k]);
        if( a[j] < a[i] ) F_SWAP(a[i],a[j]);
        if( a[j] < a[k] ) F_SWAP(a[k],a[j]);

        x=a[k];
        while (j>k & i<k) {
            do i++; while (a[i]<x);
            do j--; while (a[j]>x);

            F_SWAP(a[i],a[j]);
        }
        i++; j--;

        if (j<k) {
            while (a[i]<x) i++;
            l=i; j=m;
        }
        if (k<i) {
            while (x<a[j]) j--;
            m=j; i=l;
        }
    }
    return a[k];
}

W testach porównawczych, które tutaj zrobiłem , LefSelect jest o 20-30% szybszy niż QuickSelect.

estama
źródło
1

Rozwiązanie Haskell:

kthElem index list = sort list !! index

withShape ~[]     []     = []
withShape ~(x:xs) (y:ys) = x : withShape xs ys

sort []     = []
sort (x:xs) = (sort ls `withShape` ls) ++ [x] ++ (sort rs `withShape` rs)
  where
   ls = filter (<  x)
   rs = filter (>= x)

To implementuje medianę rozwiązań medianowych za pomocą metody withShape w celu wykrycia rozmiaru partycji bez jej obliczania.

użytkownik 3585010
źródło
1

Oto implementacja C ++ Randomized QuickSelect. Chodzi o to, aby losowo wybrać element przestawny. Aby zaimplementować losową partycję, używamy funkcji losowej, rand (), aby wygenerować indeks między l i r, zamienić element w losowo wygenerowanym indeksie na ostatni element, i na koniec wywołać standardowy proces partycjonowania, który używa ostatniego elementu jako elementu przestawnego.

#include<iostream>
#include<climits>
#include<cstdlib>
using namespace std;

int randomPartition(int arr[], int l, int r);

// This function returns k'th smallest element in arr[l..r] using
// QuickSort based method.  ASSUMPTION: ALL ELEMENTS IN ARR[] ARE DISTINCT
int kthSmallest(int arr[], int l, int r, int k)
{
    // If k is smaller than number of elements in array
    if (k > 0 && k <= r - l + 1)
    {
        // Partition the array around a random element and
        // get position of pivot element in sorted array
        int pos = randomPartition(arr, l, r);

        // If position is same as k
        if (pos-l == k-1)
            return arr[pos];
        if (pos-l > k-1)  // If position is more, recur for left subarray
            return kthSmallest(arr, l, pos-1, k);

        // Else recur for right subarray
        return kthSmallest(arr, pos+1, r, k-pos+l-1);
    }

    // If k is more than number of elements in array
    return INT_MAX;
}

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Standard partition process of QuickSort().  It considers the last
// element as pivot and moves all smaller element to left of it and
// greater elements to right. This function is used by randomPartition()
int partition(int arr[], int l, int r)
{
    int x = arr[r], i = l;
    for (int j = l; j <= r - 1; j++)
    {
        if (arr[j] <= x) //arr[i] is bigger than arr[j] so swap them
        {
            swap(&arr[i], &arr[j]);
            i++;
        }
    }
    swap(&arr[i], &arr[r]); // swap the pivot
    return i;
}

// Picks a random pivot element between l and r and partitions
// arr[l..r] around the randomly picked element using partition()
int randomPartition(int arr[], int l, int r)
{
    int n = r-l+1;
    int pivot = rand() % n;
    swap(&arr[l + pivot], &arr[r]);
    return partition(arr, l, r);
}

// Driver program to test above methods
int main()
{
    int arr[] = {12, 3, 5, 7, 4, 19, 26};
    int n = sizeof(arr)/sizeof(arr[0]), k = 3;
    cout << "K'th smallest element is " << kthSmallest(arr, 0, n-1, k);
    return 0;
}

Złożoność powyższego rozwiązania w najgorszym przypadku to nadal O (n2). W najgorszym przypadku funkcja losowa może zawsze wybrać element narożny. Oczekiwana złożoność czasowa powyższej randomizowanej funkcji QuickSelect wynosi Θ (n)

uczeń
źródło
Niezłe kodowanie. Dzięki za udostępnienie, +1
Hengameh
1
  1. Utwórz kolejkę priorytetową.
  2. Wstaw wszystkie elementy do stosu.
  3. Wywołanie ankiety () k razy.

    public static int getKthLargestElements(int[] arr)
    {
        PriorityQueue<Integer> pq =  new PriorityQueue<>((x , y) -> (y-x));
        //insert all the elements into heap
        for(int ele : arr)
           pq.offer(ele);
        // call poll() k times
        int i=0;
        while(i&lt;k)
         {
           int result = pq.poll();
         } 
       return result;        
    }
    
Bhagwati Malav
źródło
0

To jest implementacja w Javascript.

Jeśli zwolnisz ograniczenie, że nie możesz zmodyfikować tablicy, możesz zapobiec wykorzystaniu dodatkowej pamięci, używając dwóch indeksów do identyfikacji „bieżącej partycji” (w klasycznym stylu Quicksort - http://www.nczonline.net/blog/2012/ 11/27 / computer-science-in-javascript-quicksort / ).

function kthMax(a, k){
    var size = a.length;

    var pivot = a[ parseInt(Math.random()*size) ]; //Another choice could have been (size / 2) 

    //Create an array with all element lower than the pivot and an array with all element higher than the pivot
    var i, lowerArray = [], upperArray = [];
    for (i = 0; i  < size; i++){
        var current = a[i];

        if (current < pivot) {
            lowerArray.push(current);
        } else if (current > pivot) {
            upperArray.push(current);
        }
    }

    //Which one should I continue with?
    if(k <= upperArray.length) {
        //Upper
        return kthMax(upperArray, k);
    } else {
        var newK = k - (size - lowerArray.length);

        if (newK > 0) {
            ///Lower
            return kthMax(lowerArray, newK);
        } else {
            //None ... it's the current pivot!
            return pivot;
        }   
    }
}  

Jeśli chcesz przetestować jego działanie, możesz użyć tej odmiany:

    function kthMax (a, k, logging) {
         var comparisonCount = 0; //Number of comparison that the algorithm uses
         var memoryCount = 0;     //Number of integers in memory that the algorithm uses
         var _log = logging;

         if(k < 0 || k >= a.length) {
            if (_log) console.log ("k is out of range"); 
            return false;
         }      

         function _kthmax(a, k){
             var size = a.length;
             var pivot = a[parseInt(Math.random()*size)];
             if(_log) console.log("Inputs:", a,  "size="+size, "k="+k, "pivot="+pivot);

             // This should never happen. Just a nice check in this exercise
             // if you are playing with the code to avoid never ending recursion            
             if(typeof pivot === "undefined") {
                 if (_log) console.log ("Ops..."); 
                 return false;
             }

             var i, lowerArray = [], upperArray = [];
             for (i = 0; i  < size; i++){
                 var current = a[i];
                 if (current < pivot) {
                     comparisonCount += 1;
                     memoryCount++;
                     lowerArray.push(current);
                 } else if (current > pivot) {
                     comparisonCount += 2;
                     memoryCount++;
                     upperArray.push(current);
                 }
             }
             if(_log) console.log("Pivoting:",lowerArray, "*"+pivot+"*", upperArray);

             if(k <= upperArray.length) {
                 comparisonCount += 1;
                 return _kthmax(upperArray, k);
             } else if (k > size - lowerArray.length) {
                 comparisonCount += 2;
                 return _kthmax(lowerArray, k - (size - lowerArray.length));
             } else {
                 comparisonCount += 2;
                 return pivot;
             }
     /* 
      * BTW, this is the logic for kthMin if we want to implement that... ;-)
      * 

             if(k <= lowerArray.length) {
                 return kthMin(lowerArray, k);
             } else if (k > size - upperArray.length) {
                 return kthMin(upperArray, k - (size - upperArray.length));
             } else 
                 return pivot;
     */            
         }

         var result = _kthmax(a, k);
         return {result: result, iterations: comparisonCount, memory: memoryCount};
     }

Reszta kodu polega na stworzeniu placu zabaw:

    function getRandomArray (n){
        var ar = [];
        for (var i = 0, l = n; i < l; i++) {
            ar.push(Math.round(Math.random() * l))
        }

        return ar;
    }

    //Create a random array of 50 numbers
    var ar = getRandomArray (50);   

Teraz uruchom kilka testów. Z powodu Math.random () będzie generować za każdym razem inne wyniki:

    kthMax(ar, 2, true);
    kthMax(ar, 2);
    kthMax(ar, 2);
    kthMax(ar, 2);
    kthMax(ar, 2);
    kthMax(ar, 2);
    kthMax(ar, 34, true);
    kthMax(ar, 34);
    kthMax(ar, 34);
    kthMax(ar, 34);
    kthMax(ar, 34);
    kthMax(ar, 34);

Jeśli przetestujesz go kilka razy, zobaczysz nawet empirycznie, że liczba iteracji wynosi średnio O (n) ~ = stała * n, a wartość k nie wpływa na algorytm.

Chris Cinelli
źródło
0

Wymyśliłem ten algorytm i wygląda na O (n):

Powiedzmy, że k = 3 i chcemy znaleźć trzeci co do wielkości element w tablicy. Utworzyłbym trzy zmienne i porównałbym każdy element tablicy z minimum tych trzech zmiennych. Jeśli element tablicy jest większy niż nasze minimum, zmienilibyśmy zmienną min na wartość elementu. Kontynuujemy to samo do końca tablicy. Minimum trzech naszych zmiennych to 3. co do wielkości pozycja w tablicy.

define variables a=0, b=0, c=0
iterate through the array items
    find minimum a,b,c
    if item > min then replace the min variable with item value
    continue until end of array
the minimum of a,b,c is our answer

Aby znaleźć Kth największy przedmiot, potrzebujemy zmiennych K.

Przykład: (k = 3)

[1,2,4,1,7,3,9,5,6,2,9,8]

Final variable values:

a=7 (answer)
b=8
c=9

Czy ktoś może to przejrzeć i dać mi znać, czego mi brakuje?

advncd
źródło
0

Oto implementacja zaproponowanego przez eladv algorytmu (tutaj też umieszczam implementację z losową osią przestawną):

public class Median {

    public static void main(String[] s) {

        int[] test = {4,18,20,3,7,13,5,8,2,1,15,17,25,30,16};
        System.out.println(selectK(test,8));

        /*
        int n = 100000000;
        int[] test = new int[n];
        for(int i=0; i<test.length; i++)
            test[i] = (int)(Math.random()*test.length);

        long start = System.currentTimeMillis();
        random_selectK(test, test.length/2);
        long end = System.currentTimeMillis();
        System.out.println(end - start);
        */
    }

    public static int random_selectK(int[] a, int k) {
        if(a.length <= 1)
            return a[0];

        int r = (int)(Math.random() * a.length);
        int p = a[r];

        int small = 0, equal = 0, big = 0;
        for(int i=0; i<a.length; i++) {
            if(a[i] < p) small++;
            else if(a[i] == p) equal++;
            else if(a[i] > p) big++;
        }

        if(k <= small) {
            int[] temp = new int[small];
            for(int i=0, j=0; i<a.length; i++)
                if(a[i] < p)
                    temp[j++] = a[i];
            return random_selectK(temp, k);
        }

        else if (k <= small+equal)
            return p;

        else {
            int[] temp = new int[big];
            for(int i=0, j=0; i<a.length; i++)
                if(a[i] > p)
                    temp[j++] = a[i];
            return random_selectK(temp,k-small-equal);
        }
    }

    public static int selectK(int[] a, int k) {
        if(a.length <= 5) {
            Arrays.sort(a);
            return a[k-1];
        }

        int p = median_of_medians(a);

        int small = 0, equal = 0, big = 0;
        for(int i=0; i<a.length; i++) {
            if(a[i] < p) small++;
            else if(a[i] == p) equal++;
            else if(a[i] > p) big++;
        }

        if(k <= small) {
            int[] temp = new int[small];
            for(int i=0, j=0; i<a.length; i++)
                if(a[i] < p)
                    temp[j++] = a[i];
            return selectK(temp, k);
        }

        else if (k <= small+equal)
            return p;

        else {
            int[] temp = new int[big];
            for(int i=0, j=0; i<a.length; i++)
                if(a[i] > p)
                    temp[j++] = a[i];
            return selectK(temp,k-small-equal);
        }
    }

    private static int median_of_medians(int[] a) {
        int[] b = new int[a.length/5];
        int[] temp = new int[5];
        for(int i=0; i<b.length; i++) {
            for(int j=0; j<5; j++)
                temp[j] = a[5*i + j];
            Arrays.sort(temp);
            b[i] = temp[2];
        }

        return selectK(b, b.length/2 + 1);
    }
}
TheLogicGuy
źródło
0

jest podobny do strategii quickSort, w której wybieramy dowolną oś obrotu i umieszczamy mniejsze elementy po lewej, a większe po prawej

    public static int kthElInUnsortedList(List<int> list, int k)
    {
        if (list.Count == 1)
            return list[0];

        List<int> left = new List<int>();
        List<int> right = new List<int>();

        int pivotIndex = list.Count / 2;
        int pivot = list[pivotIndex]; //arbitrary

        for (int i = 0; i < list.Count && i != pivotIndex; i++)
        {
            int currentEl = list[i];
            if (currentEl < pivot)
                left.Add(currentEl);
            else
                right.Add(currentEl);
        }

        if (k == left.Count + 1)
            return pivot;

        if (left.Count < k)
            return kthElInUnsortedList(right, k - left.Count - 1);
        else
            return kthElInUnsortedList(left, k);
    }
Lee.O.
źródło
0

Można znaleźć k-ty najmniejszy element w czasie O (n) i stałej przestrzeni. Jeśli weźmiemy pod uwagę, tablica jest tylko dla liczb całkowitych.

Podejście polega na przeszukaniu binarnym zakresu wartości tablicy. Jeśli mamy wartość min_value i max_value w zakresie liczb całkowitych, możemy przeprowadzić wyszukiwanie binarne w tym zakresie. Możemy napisać funkcję komparatora, która powie nam, czy jakakolwiek wartość jest k-najmniejsza lub mniejsza niż k-ta najmniejsza lub większa niż k-ta najmniejsza. Wykonuj wyszukiwanie binarne, aż dojdziesz do k-tej najmniejszej liczby

Oto kod do tego

rozwiązanie klasy:

def _iskthsmallest(self, A, val, k):
    less_count, equal_count = 0, 0
    for i in range(len(A)):
        if A[i] == val: equal_count += 1
        if A[i] < val: less_count += 1

    if less_count >= k: return 1
    if less_count + equal_count < k: return -1
    return 0

def kthsmallest_binary(self, A, min_val, max_val, k):
    if min_val == max_val:
        return min_val
    mid = (min_val + max_val)/2
    iskthsmallest = self._iskthsmallest(A, mid, k)
    if iskthsmallest == 0: return mid
    if iskthsmallest > 0: return self.kthsmallest_binary(A, min_val, mid, k)
    return self.kthsmallest_binary(A, mid+1, max_val, k)

# @param A : tuple of integers
# @param B : integer
# @return an integer
def kthsmallest(self, A, k):
    if not A: return 0
    if k > len(A): return 0
    min_val, max_val = min(A), max(A)
    return self.kthsmallest_binary(A, min_val, max_val, k)
Anubhav Agarwal
źródło
0

Istnieje również jeden algorytm, który przewyższa algorytm szybkiego wyboru. Nazywa się to algorytmem Floyd-Rivets (FR) .

Artykuł oryginalny: https://doi.org/10.1145/360680.360694

Wersja do pobrania: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.309.7108&rep=rep1&type=pdf

Artykuł w Wikipedii https://en.wikipedia.org/wiki/Floyd%E2%80%93Rivest_algorithm

Próbowałem zaimplementować algorytm szybkiego wyboru i FR w C ++. Porównałem je również do standardowych implementacji biblioteki C ++ std :: nth_element (która jest w zasadzie hybrydą hybrydową szybkiego wyboru i heapseleksu). Wynik był szybki i nth_element działał średnio średnio, ale algorytm FR działał około. dwa razy szybciej w porównaniu do nich.

Przykładowy kod, którego użyłem dla algorytmu FR:

template <typename T>
T FRselect(std::vector<T>& data, const size_t& n)
{
    if (n == 0)
        return *(std::min_element(data.begin(), data.end()));
    else if (n == data.size() - 1)
        return *(std::max_element(data.begin(), data.end()));
    else
        return _FRselect(data, 0, data.size() - 1, n);
}

template <typename T>
T _FRselect(std::vector<T>& data, const size_t& left, const size_t& right, const size_t& n)
{
    size_t leftIdx = left;
    size_t rightIdx = right;

    while (rightIdx > leftIdx)
    {
        if (rightIdx - leftIdx > 600)
        {
            size_t range = rightIdx - leftIdx + 1;
            long long i = n - (long long)leftIdx + 1;
            long long z = log(range);
            long long s = 0.5 * exp(2 * z / 3);
            long long sd = 0.5 * sqrt(z * s * (range - s) / range) * sgn(i - (long long)range / 2);

            size_t newLeft = fmax(leftIdx, n - i * s / range + sd);
            size_t newRight = fmin(rightIdx, n + (range - i) * s / range + sd);

            _FRselect(data, newLeft, newRight, n);
        }
        T t = data[n];
        size_t i = leftIdx;
        size_t j = rightIdx;
        // arrange pivot and right index
        std::swap(data[leftIdx], data[n]);
        if (data[rightIdx] > t)
            std::swap(data[rightIdx], data[leftIdx]);

        while (i < j)
        {
            std::swap(data[i], data[j]);
            ++i; --j;
            while (data[i] < t) ++i;
            while (data[j] > t) --j;
        }

        if (data[leftIdx] == t)
            std::swap(data[leftIdx], data[j]);
        else
        {
            ++j;
            std::swap(data[j], data[rightIdx]);
        }
        // adjust left and right towards the boundaries of the subset
        // containing the (k - left + 1)th smallest element
        if (j <= n)
            leftIdx = j + 1;
        if (n <= j)
            rightIdx = j - 1;
    }

    return data[leftIdx];
}

template <typename T>
int sgn(T val) {
    return (T(0) < val) - (val < T(0));
}
L'ahim
źródło
-1

Chciałbym to zrobić:

initialize empty doubly linked list l
for each element e in array
    if e larger than head(l)
        make e the new head of l
        if size(l) > k
            remove last element from l

the last element of l should now be the kth largest element

Możesz po prostu przechowywać wskaźniki do pierwszego i ostatniego elementu na połączonej liście. Zmieniają się one tylko po dokonaniu aktualizacji listy.

Aktualizacja:

initialize empty sorted tree l
for each element e in array
    if e between head(l) and tail(l)
        insert e into l // O(log k)
        if size(l) > k
            remove last element from l

the last element of l should now be the kth largest element
Jasper Bekkers
źródło
Co jeśli e jest mniejsze niż głowa (l)? Może nadal być większy niż k-ty największy element, ale nigdy nie zostanie dodany do tej listy. Aby to zadziałało, musisz posortować listę elementów w porządku rosnącym.
Elie
Masz rację, myślę, że będę musiał przemyśleć to jeszcze trochę. :-)
Jasper Bekkers
Rozwiązaniem byłoby sprawdzenie, czy e znajduje się między głową (l) a ogonem (l) i włożenie go we właściwe położenie, jeśli tak jest. Wykonanie tego O (kn). Możesz zrobić to O (n log k), gdy używasz drzewa binarnego, które śledzi minimalne i maksymalne elementy.
Jasper Bekkers
-1

Najpierw możemy zbudować BST z nieposortowanej tablicy, która zajmuje O (n) czasu, a z BST możemy znaleźć k-ty najmniejszy element w O (log (n)), który w sumie liczy się do rzędu O (n).

użytkownik2601131
źródło