Wie finde ich das k-größte Element in einem unsortierten Array der Länge n in O (n)?
Ich glaube, es gibt eine Möglichkeit, das k-te größte Element in einem unsortierten Array der Länge n in O (n) zu finden. Oder vielleicht ist es "erwartet" O(n) oder so. Wie können wir das machen?
Dies wird als Finden der k-ten Ordnungsstatistik bezeichnet. Es gibt einen sehr einfachen randomisierten Algorithmus (genannt Quickselect), der O(n) Durchschnittszeit, O(n^2) Worst-Case-Zeit und einen ziemlich komplizierten, nicht-randomisierten Algorithmus (introselect) unter O(n) im schlimmsten Fall. Es gibt einige Informationen zu Wikipedia , aber es ist nicht sehr gut.
Alles, was Sie brauchen, ist in diese PowerPoint-Folien. Um den grundlegenden Algorithmus des O(n) Worst-Case-Algorithmus (Introselect) zu extrahieren:
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)
Es ist auch sehr schön im Buch Einführung in Algorithmen von Cormen et al.
Wenn Sie einen echten O(n)-Algorithmus wollen, im Gegensatz zu O(kn) oder ähnlichem, sollten Sie quickselect verwenden (im Grunde ist es quicksort, wo Sie die Partition rauswerfen, die Sie nicht interessiert). Mein prof hat eine tolle Beschreibung, mit der Laufzeitanalyse: ( Referenz )
Der QuickSelect-Algorithmus findet schnell das k-te kleinste Element eines unsortierten Arrays von n Elementen. Es ist ein RandomizedAlgorithm , also berechnen wir die im schlimmsten Fall erwartete Laufzeit.
Hier ist der Algorithmus.
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
Was ist die Laufzeit dieses Algorithmus? Wenn der Gegner Münzen für uns wirft, stellen wir möglicherweise fest, dass der Drehpunkt immer das größte Element ist und k immer 1 ist, was eine Laufzeit von ergibt
T(n) = Theta(n) + T(n-1) = Theta(n2)Aber wenn die Auswahl tatsächlich zufällig ist, ist die erwartete Laufzeit gegeben durch
T(n) <= Theta(n) + (1/n) ∑i=1 to nT(max(i, n-i-1))wobei wir die nicht ganz vernünftige Annahme treffen, dass die Rekursion immer im größeren von A1 oder A2 landet.
Lassen Sie uns raten, dass T(n) <= an für einige a. Dann bekommen wir
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 aiund jetzt müssen wir irgendwie die horrende Summe rechts vom Pluszeichen bekommen, um das cn links aufzunehmen. Wenn wir es nur als 2(1/n) ∑i=n/2 to n an binden, erhalten wir ungefähr 2(1/n)(n/2)an = an. Aber das ist zu groß - es gibt keinen Platz, um ein zusätzliches cn einzudrücken. Erweitern wir also die Summe mit der arithmetischen Reihenformel:
∑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)n2wobei wir den Vorteil ausnutzen, dass n "ausreichend groß" ist, um die hässlichen floor(n/2) -Faktoren durch die viel saubereren (und kleineren) n/4 zu ersetzen. Jetzt können wir weitermachen
cn + 2 (1/n) ∑i=floor(n/2) to n ai,
<= cn + (2a/n) (15/32) n2
= n (c + (15/16)a)
<= anbereitgestellt a > 16c.
Dies gibt T(n) = O(n). Es ist eindeutig Omega(n), also bekommen wir T(n) = Theta(n).
Ein schnelles Google über dieses ('k-tes größtes Element-Array') gab Folgendes zurück: http://discuss.joelonsoftware.com/default.asp?interview.11.509587.17
"Make one pass through tracking the three largest values so far."
(es war speziell für 3d größten)
und diese Antwort:
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)
Sie mögen Quicksortieren. Wähle ein Element nach dem Zufallsprinzip und schiebe alles höher oder tiefer. An diesem Punkt wissen Sie, welches Element Sie tatsächlich ausgewählt haben, und wenn es das k-te Element ist, sind Sie fertig, andernfalls wiederholen Sie mit der Ablage (höher oder niedriger), dass das k-te Element in den Raum fallen würde. Statistisch gesehen die Zeit um zu finden, wächst das k-te Element mit n, O (n).
Begleiter eines Programmierers für die Algorithmusanalyse gibt eine Version an, die ist O (n), obwohl der Autor angibt, dass der konstante Faktor so hoch ist, würden Sie wahrscheinlich die naive Sortierliste vorziehen -Methode auswählen.
Ich habe den Brief Ihrer Frage beantwortet :)
Die C++ - Standardbibliothek hat fast genau diese Funktion call nth_element, obwohl sie Ihre Daten ändert. Es hat eine lineare Laufzeit O (N) erwartet und führt auch eine teilweise Sortierung durch.
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
Obwohl nicht sehr sicher über O(n) Komplexität, aber es wird sicher zwischen O(n) und nLog (n) liegen. Stellen Sie außerdem sicher, dass Sie sich näher an O(n) als nLog (n) befinden. Funktion ist in Java geschrieben
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;
}
}
Ich habe das Finden des k-ten Minimums in n unsortierten Elementen mit dynamischer Programmierung, speziell der Turniermethode, implementiert. Die Ausführungszeit ist O (n + klog (n)). Der verwendete Mechanismus ist auf Wikipedia-Seite als eine der Methoden zum Auswahlalgorithmus aufgeführt (wie in einem der obigen Einträge angegeben). Sie können den Algorithmus lesen und auch Code (Java) auf meiner Blogseite finden Finding Kth Minimum . Zusätzlich kann die Logik die Liste teilweise sortieren - erste K min (oder max) in der Zeit O(klog(n)) zurückgeben.
Obwohl der Code das k-te Minimum liefert, kann eine ähnliche Logik verwendet werden, um das k-te Maximum in O (klog (n)) zu finden, wobei die Vorarbeit zum Erstellen des Turnierbaums ignoriert wird.
Sie können dies in O (n + kn) = O(n) (für konstante k) für die Zeit und O(k) für den Raum tun, indem Sie die k größten Elemente verfolgen, die Sie haben gesehen.
Für jedes Element im Array können Sie die Liste der größten k durchsuchen und das kleinste Element durch das neue ersetzen, falls es größer ist.
Warrens vorrangige Heap-Lösung ist jedoch ordentlicher.
Nachfolgend finden Sie den Link zur vollständigen Implementierung mit einer ausführlichen Erklärung, wie der Algorithmus zum Finden des K-ten Elements in einem unsortierten Algorithmus funktioniert. Grundidee ist, das Array wie in QuickSort zu partitionieren. Um jedoch extreme Fälle zu vermeiden (z. B. wenn das kleinste Element in jedem Schritt als Drehpunkt gewählt wird, so dass der Algorithmus zur Laufzeit O (n ^ 2) degeneriert), wird eine spezielle Drehpunktauswahl angewendet, die als Median-of-Medians-Algorithmus bezeichnet wird. Die gesamte Lösung läuft im schlechtesten und im durchschnittlichen Fall in der Zeit O(n).
Hier ist der Link zum vollständigen Artikel (es geht darum, das Kth kleinste Element zu finden, aber das Prinzip ist das gleiche, um das Kth größte zu finden):
Sexy Schnellselektion in Python
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]
Suchen Sie den Median des Arrays in linearer Zeit, und verwenden Sie dann die Partitionsprozedur genau wie in quicksort, um das Array in zwei Teile zu teilen, wobei die Werte links vom Median kleiner (<) als Median und rechts größer als (>) sind , das kann man auch in der linearen Zeit machen, gehe jetzt zu dem Teil des Arrays, in dem das k-te Element liegt, Nun wird die Wiederholung zu: T (n) = T(n/2) + cn was mir O (n) overal gibt.
Gemäß diesem Artikel Auffinden des K-größten Elementes in einer Liste von n Elementen benötigt der folgende Algorithmus im schlechtesten Fall O(n).
- Teilen Sie das Array in n/5 Listen mit jeweils 5 Elementen.
- Suchen Sie den Median in jedem Sub-Array mit 5 Elementen.
- Suchen Sie rekursiv den Median aller Mediane, nennen wir ihn M
- Partitionieren Sie das Array in zwei Subarrays. Das erste Subarray enthält die Elemente, die größer als M sind. Nehmen wir an, dieses Subarray ist a1, während das andere Subarray die Elemente enthält, die kleiner als M sind.
- Wenn k <= | a1 |, Auswahl zurückgeben (a1, k).
- Wenn k− 1 = | a1 | ist, M zurückgeben.
- Wenn k> | a1 | + 1, Rückgabe Auswahl (a2, k −a1 - 1).
Analyse: Wie in der Originalarbeit vorgeschlagen:
Wir verwenden den Median, um die Liste in zwei Hälften zu unterteilen (die erste Hälfte, Falls
k <= n/2und die zweite Hälfte sonst). Dieser Algorithmus dauert Zeitcnauf der ersten Rekursionsstufe für eine Konstantec,cn/2um die nächste Ebene (da wir in einer Liste der Größe n/2 wiederkehren),cn/4am dritte Ebene und so weiter. Die insgesamt benötigte Zeit istcn + cn/2 + cn/4 + .... = 2cn = o(n).
Warum ist die Partitionsgröße 5 und nicht 3?
Wie in Original Papier erwähnt :
Wenn Sie die Liste durch 5 teilen, ist eine Aufteilung des schlechtesten Falls von 70 - 30 gewährleistet. die Hälfte der Mediane ist größer als der Median der Mediane, daher mindestens Die Hälfte der n/5 Blöcke hat mindestens 3 Elemente und dies ergibt eine
3n/10split, was bedeutet, dass die andere Partition im schlimmsten Fall 7n/10 ist . Das gibtT(n) = T(n/5)+T(7n/10)+O(n). Since n/5+7n/10 < 1, das Worst-Case-Laufzeit istO(n).
Jetzt habe ich versucht den obigen Algorithmus zu implementieren als:
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];
}
Nur zur Vervollständigung verwendet ein anderer Algorithmus die Prioritätswarteschlange und nimmt Zeit in Anspruch 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;
}
Beide Algorithmen können getestet werden als:
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));
}
Die erwartete Ausgabe lautet: 18
18
Wie wäre es mit dieser Art von Ansatz
Behalten Sie einen buffer of length k und einen tmp_max bei, tmp_max zu bekommen ist O(k) und wird n-mal gemacht, so etwas wie O(kn)
Ist es richtig oder fehlt mir etwas?
Obwohl es den Durchschnittsfall der Schnellauswahl und den schlechtesten Fall der Median-Statistikmethode nicht übertrifft, ist es doch ziemlich einfach zu verstehen und zu implementieren.
durchlaufen Sie die Liste. Wenn der aktuelle Wert größer als der gespeicherte größte Wert ist, speichern Sie ihn als den größten Wert, und drücken Sie die Tasten 1-4 nach unten, und 5 werden aus der Liste entfernt. Wenn nicht, vergleiche es mit Nummer 2 und mache dasselbe. Wiederholen Sie diesen Vorgang und vergleichen Sie alle 5 gespeicherten Werte. das sollte es in O (n) tun
Es gibt auch den Wirth-Auswahlalgorithmus , der eine einfachere Implementierung als QuickSelect aufweist. Wirths Auswahlalgorithmus ist langsamer als QuickSelect, wird jedoch mit einigen Verbesserungen schneller.
Genauer. Mit der MODIFIND-Optimierung von Vladimir Zabrodsky und dem Pivot-Median-of-3-Pivot und der letzten Etappe des Partitionierungsteils des Algorithmus habe ich den folgenden Algorithmus entwickelt (denkbar "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];
}
In Benchmarks, die ich hier gemacht habe, ist LefSelect 20-30% schneller als QuickSelect.
Hier ist eine C++ - Implementierung von Randomized QuickSelect. Die Idee ist, ein Pivotelement zufällig auszuwählen. Um eine randomisierte Partition zu implementieren, verwenden wir eine Random-Funktion, Rand (), um den Index zwischen l und r zu generieren, das Element bei einem zufällig generierten Index mit dem letzten Element zu tauschen und schließlich den Standardpartitionsprozess aufzurufen, der das letzte Element als Pivot verwendet.
#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;
}
Die Zeitkomplexität im ungünstigsten Fall der obigen Lösung ist immer noch O (n2). Im ungünstigsten Fall kann die randomisierte Funktion immer ein Eckelement auswählen. Die erwartete Zeitkomplexität von randomized QuickSelect ist Θ (n).
Erklärungen zum Median-of-Medians-Algorithmus zum Finden der k-ten größten Ganzzahl von n finden Sie hier: http://cs.indstate.edu/~spitla/presentation.pdf
Implementierung in C++ ist unten:
#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;
}
Haskell-Lösung:
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)
Dies implementiert den Median der Medianlösungen, indem die withShape-Methode verwendet wird, um die Größe einer Partition zu ermitteln, ohne sie tatsächlich zu berechnen.
- Prioritätswarteschlange erstellt haben.
- Fügen Sie alle Elemente in den Heap ein.
Aufruf poll () k mal.
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<k) { int result = pq.poll(); } return result; }
ich möchte eine Antwort vorschlagen
wenn wir die ersten k Elemente nehmen und in eine verknüpfte Liste von k Werten sortieren
jetzt für jeden anderen Wert, selbst für den ungünstigsten Fall, wenn die Einfügungssortierung für rest-nk-Werte durchgeführt wird, selbst im schlimmsten Fall wird die Anzahl der Vergleiche k * (nk) sein, und für prev-k-Werte gilt: 1) so kommt es zu (nk-k), was o (n) ist
prost
Ich habe mir diesen Algorithmus ausgedacht und scheint O (n) zu sein:
Sagen wir k = 3 und wir wollen das drittgrößte Element im Array finden. Ich würde drei Variablen erstellen und jedes Element des Arrays mit dem Minimum dieser drei Variablen vergleichen. Wenn das Array-Element größer ist als unser Minimum, würden wir die Variable min durch den Elementwert ersetzen. Wir setzen das gleiche bis zum Ende des Arrays fort. Das Minimum unserer drei Variablen ist das drittgrößte Element im Array.
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
Um das größte K-Element zu finden, benötigen wir K-Variablen.
Beispiel: (k = 3)
[1,2,4,1,7,3,9,5,6,2,9,8]
Final variable values:
a=7 (answer)
b=8
c=9
Kann jemand dies bitte überprüfen und mich wissen lassen, was mir fehlt?
Gehe zum Ende dieses Links: ...........
Hier ist die Implementierung des Algorithmus eladv vorgeschlagen (ich habe hier auch die Implementierung mit zufälligem Pivot eingefügt):
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);
}
}
Sie finden das k-kleinste Element in O(n) Zeit und konstantem Raum. Wenn wir bedenken, dass das Array nur für ganze Zahlen ist.
Der Ansatz besteht darin, eine binäre Suche im Bereich der Array-Werte durchzuführen. Wenn wir sowohl einen min_value als auch einen max_value im ganzzahligen Bereich haben, können wir eine binäre Suche in diesem Bereich durchführen. Wir können eine Komparatorfunktion schreiben, die uns sagt, ob irgendein Wert der k-te kleinste oder kleiner als k-te der kleinste ist oder größer als k-te kleinste . Führen Sie die binäre Suche aus, bis Sie die k-te kleinste Zahl erreichen
Hier ist der Code dafür
klassenlösung:
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)
Es gibt auch einen Algorithmus, der den Quickselect-Algorithmus übertrifft. Es heißt Floyd-Rivets (FR) -Algorithmus.
Originalartikel: https://doi.org/10.1145/360680.360694
Herunterladbare Version: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.309.7108&rep=rep1&type=pdf
Wikipedia-Artikel https://en.wikipedia.org/wiki/Floyd%E2%80%93Rivest_algorithm
Ich habe versucht, den Quickselect- und den FR-Algorithmus in C++ zu implementieren. Ich habe sie auch mit den Standardimplementierungen der C++ - Bibliothek verglichen, nämlich std :: nth_element (was im Grunde eine Introselect-Hybride aus quickselect und heapselect ist). Das Ergebnis war "quickselect" und nth_element lief im Durchschnitt vergleichbar, aber der FR-Algorithmus lief ca. doppelt so schnell im Vergleich zu ihnen.
Beispielcode, den ich für den FR-Algorithmus verwendet habe:
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));
}
diese Strategie ähnelt der quickSort-Strategie, bei der wir einen beliebigen Drehpunkt auswählen und die kleineren Elemente nach links und die größeren nach rechts bringen
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);
}
Dies ist eine Implementierung in Javascript.
Wenn Sie die Einschränkung freigeben, dass Sie das Array nicht ändern können, können Sie die Verwendung von zusätzlichem Speicher verhindern, indem Sie zwei Indizes verwenden, um die "aktuelle Partition" zu identifizieren (im klassischen Quicksort-Stil - http://www.nczonline.net/blog/ 2012/11/27/Informatik-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;
}
}
}
Wenn Sie testen möchten, wie es funktioniert, können Sie diese Variante verwenden:
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};
}
Der Rest des Codes dient nur zum Erstellen eines Spielplatzes:
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);
Führen Sie nun einige Tests aus. Durch Math.random () wird es jedes Mal andere Ergebnisse liefern:
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);
Wenn Sie es einige Male testen, können Sie sogar empirisch feststellen, dass die Anzahl der Iterationen im Durchschnitt O(n) ~ = konstant * n ist und der Wert von k den Algorithmus nicht beeinflusst.