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

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ć?

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.

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

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)

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

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

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

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

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.

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.

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]

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.

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

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

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)

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.

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)

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

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

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.

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.

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)

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

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.

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?

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);
    }
}

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);
    }

Idź do końca tego linku: ...........

http://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array-set-3-worst-case-linear-time/

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)

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));
}

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

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