Ich möchte hier einen Algorithmus besprechen, den ich in einem Datenstrukturbuch gefunden habe. Dieses Buch präsentiert eine Skizze des Algorithmus, um das Majoritätselement (erscheint mehr als N / 2) in einem Array der Größe N zu finden. Die Skizze des Algorithmus ist wie folgt:
Zuerst wird ein Kandidatenmehrheitselement gefunden (dies ist der schwierigere Teil). Dieser Kandidat ist das einzige Element, das möglicherweise das Mehrheitselement sein könnte. Der zweite Schritt bestimmt, ob dieser Kandidat tatsächlich die Mehrheit ist. Dies ist nur eine sequentielle Suche durch das Array. Um einen Kandidaten im Array A zu finden, bilden Sie ein zweites Array B. Vergleichen Sie dann A1, A2. Wenn sie gleich sind, füge einen von diesen zu B hinzu; sonst tu nichts. Dann vergleiche A3 und A4. Wenn sie gleich sind, füge einen von diesen zu B hinzu; sonst tu nichts. Fahren Sie auf diese Weise fort, bis das gesamte Array gelesen wurde. Suchen Sie dann rekursiv einen Kandidaten für B; Dies ist der Kandidat für A.
Ich habe herausgefunden, wenn das N gerade ist, Algorithmus funktioniert gut. Aber was, wenn N ungerade ist? Wie können wir mit diesem Fall umgehen?
Mehrheitselement:
Ein Majoritätselement in einem Array A [] der Größe n ist ein Element, das mehr als n / 2 mal erscheint (und daher gibt es höchstens ein solches Element).
Suche nach einem Kandidaten:
Der Algorithmus für die erste Phase, der in O (n) arbeitet, ist als Moores Voting-Algorithmus bekannt. Grundlegende Idee des Algorithmus ist, wenn wir jedes Vorkommen eines Elements e mit allen anderen Elementen, die sich von e unterscheiden, ausschließen, dann existiert e bis zum Ende, wenn es ein Mehrheitselement ist.
%Vor%Der obige Algorithmus durchläuft jedes Element und führt eine Zählung von [maj_index]. Wenn das nächste Element gleich ist, wird die Zählung inkrementiert, wenn das nächste Element nicht gleich ist, wird die Zählung dekrementiert, und wenn die Zählung 0 erreicht, ändert sich der maj_index zu dem aktuellen Element und setzt die Anzahl auf 1. First Phase Algorithmus gibt uns ein Kandidatenelement. In der zweiten Phase müssen wir prüfen, ob der Kandidat tatsächlich ein Mehrheitselement ist.
Die zweite Phase ist einfach und kann leicht in O (n) durchgeführt werden. Wir müssen nur überprüfen, ob die Anzahl der Kandidatenelemente größer als n / 2 ist.
Der Algorithmus, den Sie erklärt haben, funktioniert nach folgender Idee:
Wenn zwei aufeinanderfolgende Elemente gleich sind, dann ist dies das potentielle Mehrheitselement und schließt es in die Ergebnismenge ein (zur weiteren Verarbeitung)
Wenn zwei Elemente verschieden sind, entscheidet dieses bestimmte Paar nicht über den Gewinner.
Punkt # 2 ist entscheidend - angenommen, dass das (A1, A2) Paar das Mehrheitselement (A1) und ein anderes Minoritätselement (A2) enthält. Entferne dieses Paar. A1 bleibt die Mehrheit im Rest des Arrays.
Wenn Sie diese Erklärung verstanden haben, dann verstehen Sie, warum B nichts hinzugefügt wird, wenn Elemente sich unterscheiden.
Eine Korrlaration zum Algorithmus wäre dann in Bezug auf ein Array mit einer ungeraden Anzahl von Elementen wie folgt: füge ein ungerades Element zu B hinzu. Grund ist das gleiche wie # 1: es könnte das Mehrheitselement sein und es sollte in der Ausgabe nur um sicher zu sein, dass seine Anzahl nicht in dem Prozess verloren geht.
Wie auch immer, die ganze Sache kann ohne das andere Array B gemacht werden. Hier finden Sie viel einfacheren Algorithmus: Ein Mehrheitselement in einem Array finden
Hier sind drei Algorithmen, die das Problem lösen:
1) Scanne die Elemente des Arrays, akkumuliere eine Häufigkeit jedes einzelnen Elements mit Hilfe einer Art Wörterbuch (Hash-Tabelle, ausgeglichener Baum). Wenn der Scanvorgang abgeschlossen ist, wählen Sie das einzige Wörterbuchelement aus, dessen Anzahl größer als n / 2 ist, oder melden Sie, dass kein Element eine Mehrheit aufweist.
2) Das Majoritätselement muss der Median des Arrays sein, wenn es existiert. Berechnen Sie den Median mit der Median-of-Five-Methode oder einem anderen Algorithmus und bestätigen Sie, dass er größer als n / 2 ist.
3) Ein Algorithmus von Boyer und Moore (die gleichen Typen, die den String-Matching-Algorithmus verwenden) wählt das erste Array-Element als Kandidatenelement aus, weist einen Zählerstand von 1 zu und durchsucht dann das Array das nächste Element ist das gleiche wie der aktuelle Kandidat, subtrahiert 1 vom Zählwert, wenn das nächste Element vom aktuellen Kandidat abweicht, und setzt den Kandidaten auf das nächste Arrayelement mit einer Zählung von 1 zurück, sobald der Zählwert 0 erreicht Ende des Scans ist der aktuelle Kandidat ein Mitglied der Mehrheit, wenn eine Mehrheit vorhanden ist, so dass ein zweiter Scan erforderlich ist, um zu bestätigen, dass der Kandidat eine Mehrheit bildet.
Ich bespreche und implementiere alle drei Algorithmen in meinem Blog .
Ich denke, Ihr Algorithmus wird nicht funktionieren, wenn N auch nur ist. Ich kann es mit einem Beispiel beweisen:
Betrachte ein Array von 8 Elementen, sagen wir 2,2,1,1,3,2,2,2. Jetzt wird Ihr B-Array nach Ihrer Aussage 2,1,2 sein. Wenn Sie den obigen Schritt wiederholen. Es wird keine Kandidaten geben. Aber die tatsächliche Antwort ist hier "2". Also diese Methode ist definitiv falsch.
Dieses Problem wurde auf Geeks für Geeks diskutiert. Ich denke, das wird dir helfen:
Tags und Links algorithm