Ich habe ein Array der Größe 1000. Wie kann ich die Indizes (Indizes) der fünf maximalen Elemente finden?
Ein Beispiel mit Setup-Code und meinem Versuch wird unten angezeigt:
%Vor% Ich weiß, dass das Problem darin besteht, dass allen maximalen Elementen ständig der höchste Maximalwert zugewiesen wird. Ich bin mir nicht sicher, wie ich das beheben kann, weil ich die Werte und die Indizes von myArray beibehalten muss.
Ich glaube nicht, dass Sortieren eine Option ist, weil ich die Indizes beibehalten muss. Tatsächlich sind es die Indizes, die ich spezifisch brauche.
Das Sortieren ist eine Option, auf Kosten von zusätzlichem Speicher. Betrachten Sie den folgenden Algorithmus.
%Vor%Also ist Schritt 4 (n * lg n), genau wie die Sorte. Der gesamte Algorithmus ist n lg n und ist sehr einfach zu programmieren.
Hier ist ein schnelles und schmutziges Beispiel. Es kann Fehler geben, und offensichtlich kommen Null-Überprüfung und dergleichen ins Spiel.
importieren Sie java.util.Arrays;
%Vor% Es gibt noch andere Dinge, die Sie tun können, um den Overhead dieser Operation zu reduzieren. Zum Beispiel könnten Sie anstatt einer Sortierung eine Warteschlange verwenden, die nur die größten 5 verfolgt. Being int s Diese Werte müssten wahrscheinlich in einer Box platziert werden, um sie einer Sammlung hinzuzufügen (es sei denn, Sie haben Ihre eigene Rolle gerollt) deutlich.
ein bisschen spät in der Antwort, könnten Sie auch diese Funktion, die ich schrieb:
%Vor% Meine schnelle und ein bisschen "über den Tellerrand denken" Idee wäre die Verwendung des EvictingQueue , die maximal 5 Elemente enthält. Du hättest es mit den ersten fünf Elementen aus deinem Array füllen müssen (mach es in aufsteigender Reihenfolge, also ist das erste Element, das du hinzufügst, das niedrigste von den fünf).
Dann müssen Sie das Array durchlaufen und der Warteschlange ein neues Element hinzufügen, wenn der aktuelle Wert größer als der niedrigste Wert in der Warteschlange ist. Um sich an die Indizes zu erinnern, erstellen Sie ein Wrapper-Objekt (ein Wert / Index-Paar).
Nach der Iteration durch das gesamte Array haben Sie Ihre fünf Maximalwert / Index-Paare in der Warteschlange (in absteigender Reihenfolge).
Es ist eine O (n) Lösung.
Arrays.sort (myArray), dann nimm die letzten 5 Elemente.
Sortieren Sie eine Kopie, wenn Sie die ursprüngliche Reihenfolge beibehalten möchten.
Wenn Sie die Indizes haben wollen, gibt es keine schnelle Lösung wie in Python oder anderen Sprachen. Sie sortieren und scannen, aber das ist hässlich.
Oder du könntest obszön gehen - das ist schließlich Java. Erstellen Sie ein ArrayMaxFilter-Objekt. Es wird eine private Klasse ArrayElement haben, die aus einem Index und einem Wert besteht und eine natürliche Ordnung nach Wert hat. Es wird eine Methode haben, die ein Paar von Ints, Index und Wert annimmt, ein ArrayElement von ihnen erstellt und sie in eine Prioritätswarteschlange der Länge 5 ablegt (oder wie viele Sie auch finden wollen). Übergeben Sie jedes Index / Wert-Paar vom Array und geben Sie dann die in der Warteschlange verbleibenden Werte aus. (Ja, eine Prioritätswarteschlange behält traditionell die niedrigsten Werte, aber Sie können dies in Ihrer Implementierung spiegeln)
Hier ist meine Lösung. Erstellen Sie eine Klasse, die ein Indice mit einem Wert kombiniert:
%Vor%und dann verwenden Sie diese Klasse in Ihrer Hauptmethode:
%Vor%und Beispielausgabe von einem Lauf:
%Vor% Das von mir bereitgestellte Beispiel erzeugt nur zehn Eingänge mit einem Wert zwischen 0 und 99, so dass ich sehen konnte, dass es funktioniert hat. Sie können dies leicht ändern, um 1000 Werte jeder Größe anzupassen. Anstatt 3 für Schleifen separat auszuführen, habe ich überprüft, ob der neueste Wert, den ich hinzufüge, ein Maximalwert ist, direkt nachdem ich zu myArray hinzugefügt habe. Lass es laufen und schau, ob es für dich funktioniert.