Nehmen wir an, wir haben einen Vektor / ein Array in C ++ und wir möchten zählen, welches dieser N Elemente maximale Wiederholungen hat und die höchste Anzahl ausgeben. Welcher Algorithmus ist für diesen Job am besten geeignet?
Beispiel:
%Vor%Der Ausgang ist 4, weil 2 viermal auftritt. Das ist die maximale Häufigkeit, mit der 2 auftritt.
Sortieren Sie das Array und machen Sie dann einen schnellen Durchlauf, um jede Zahl zu zählen. Der Algorithmus hat eine O (N * logN) -Komplexität.
Alternativ können Sie eine Hash-Tabelle erstellen, indem Sie die Nummer als Schlüssel verwenden. Speichern Sie in der Hash-Tabelle einen Zähler für jedes Element, das Sie eingegeben haben. Sie können alle Elemente in einem Durchgang zählen. Die Komplexität des Algorithmus hängt jedoch von der Komplexität Ihrer Hasing-Funktion ab.
Für den Weltraum optimiert:
Quicksort (zum Beispiel) dann iterieren über die Elemente, nur die größte Anzahl verfolgen. Am besten O (N log N).
Optimiert für Geschwindigkeit:
Iteriere über alle Elemente und behalte die einzelnen Zählungen im Auge. Dieser Algorithmus wird immer O (n) sein.
Wenn Sie RAM haben und Ihre Werte nicht zu groß sind, verwenden Sie counting sort .
Eine mögliche C ++ - Implementierung, die STL verwendet, könnte sein:
%Vor%Der Hash-Algorithmus (Build-Anzahl [i] = #Occurrences (i) in grundsätzlich linearer Zeit) ist sehr praktisch, ist aber theoretisch nicht streng O (n), da während des Prozesses Hash-Kollisionen auftreten könnten.
Ein interessanter Sonderfall dieser Frage ist der Mehrheitsalgorithmus, bei dem Sie ein Element finden wollen, das in mindestens n / 2 der Array-Einträge vorhanden ist, falls ein solches Element existiert.
Hier ist eine kurze Erklärung und ein eine ausführlichere Erklärung , wie man das in linearer Zeit ohne irgendeine Art von Hasch-Trickiness macht.
Wenn der Bereich der Elemente im Vergleich zur Anzahl der Elemente groß ist, würde ich, wie andere gesagt haben, einfach sortieren und scannen. Dies ist die Zeit n * log n und kein zusätzlicher Speicherplatz (vielleicht log n zusätzlich).
Das Problem mit der Zählsortierung ist, dass es, wenn der Wertebereich groß ist, länger dauern kann, das Zählarray zu initialisieren als zu sortieren.
Hier ist meine vollständige, getestete Version mit std::tr1::unordered_map .
Ich mache das ungefähr O (n). Erstens durchläuft es die n Eingabewerte, um die Zählungen in unordered_map einzufügen / zu aktualisieren, und dann führt es eine partial_sort_copy durch, die O (n) ist. 2 * O (n) ~ = O (n).
Es wird in O (n) sein ............ aber das Ding ist das große Nein. des Arrays kann ein anderes Array mit der gleichen Größe ............
einnehmenfür (i = 0; i
mar = zählen [o]; Index = o;
für (i = 0; i
dann ist die Ausgabe ......... das Element index ist für max no aufgetreten. von Zeiten in diesem Array ........
hier ein [] ist das Datenfeld, wo wir das Maximum von bestimmten Nr. suchen müssen. in einem Array .......
count [] mit der Anzahl jedes Elements .......... Hinweis: Wir wissen, dass der Datenbereich im Array liegt. sag für zB. die Daten in diesem Array liegen im Bereich von 1 bis 100 ....... dann haben sie das Zählarray von 100 Elementen, um den Überblick zu behalten, wenn sie aufgetreten sind, erhöhen sie den indizierten Wert um eins ........