Ich möchte den Rang jedes Elements in einem Array herausfinden, das bei 0 beginnt.
Beispiel:
%Vor%Erläuterung:
%Vor% Was ich ausprobiert habe, ist n^2 time complexity algorithm. Ich möchte einen Algorithmus mit linearer zeitlicher Komplexität O(n) .
Jemand hat mir im Kommentarbereich eine Lösung dafür gegeben, aber sein Kommentar wurde gelöscht. Ich weiß nicht wie. Das funktioniert korrekt für negative ganze Zahlen und positive ganze Zahlen sowie sehr große Liste.
Danke an den Autor
%Vor%Also mit Rang meinen Sie die Position, wo dieses Element nach dem Sortieren des Arrays landen würde?
Sie können mit einer Identitätsabbildung map = {0,1,2} beginnen und diese dann sortieren, aber Ihren arr als Sortierschlüssel verwenden.
Auf diese Weise ändern Sie nicht Ihr ursprüngliches Array, sondern erhalten eine Zuordnung von Ihren Array-Elementen zu ihrem Rang.
Offensichtlich hängt dieser Algorithmus von der Komplexität Ihres Sortieralgorithmus ab. Sie sollten mit O (n log n) enden, aber vielleicht erlauben es Ihre Daten, Sortieralgorithmen mit O (n) -Komplexität zu verwenden. Aber das hängt wirklich davon ab, was Sie in Ihrer großen Liste speichern.
sortiert zuerst alle Elemente und speichert sie in einem anderen Array (wenn die Elemente unsortiert sind) Drucken Sie dann den Element-Index aus diesem Array.
Ich gebe eine Idee. Wenn Sie möchten, können Sie dies verwenden:
%Vor%count_array aus dem Eingabearray nach counting sort technique (Beispiel: array = {2, 1, 3}, So count_array = {0,1,1,1} // hier array value verwenden als% Code%). count_array index value wie count_array // du nur result_array = {0, 1, 2, 3} filtern (du kannst das auch in add 1 with previous added value if count_array[i] == 1 machen. Ich benutze count_array um nur zu verstehen) result _array von rank_array By result_array
rank_array[i] = result_array[array[i]] - 1 mit rank_array finden
Beispiel:
%Vor%in Java 8, erstes Array zum Auflisten, dann zum Streamen. wegen nur einer Schleife im Strom sollte es O (n) sein.
%Vor%Ergebnis: {1,0,2}
Es ist möglich, diesen Rang unter Verwendung einer Datenstruktur zu berechnen, die "Ordnungsstatistikbaum" genannt wird, es ist eine erweiterte Datenstruktur. Um diese Struktur zu implementieren, müssen Sie einen ausgeglichenen Binärbaum (z. B. AVL-Baum oder Rot-Schwarz-Baum) implementieren, und Sie fügen jedem Knoten ein zusätzliches Attribut hinzu. Dies ist ein sehr effizienter Weg, um Ränge zu berechnen, da für jedes Element O (lg n) (wobei lg der Logarithmus der Basis 2 ist) benötigt wird. Weitere Informationen zu dieser Datenstruktur finden Sie in "Einführung in Algorithmen" in Kapitel 14.
Das Problem mit der Sortierung ist, dass die Laufzeit O (nlog (n)) ist und ich denke, dass es ineffizient ist, wenn Sie wenige Elemente rangieren möchten (d. h. weniger als n Elemente).
Tags und Links algorithm java arrays time-complexity