zu finden, wenn es eine Zahl in einem Array ist, das mehr als n/8-mal

Question

erscheint die Frage ist:

einen Algorithmus beschreiben, die in O (n) Zeit finden, wenn es in einer Reihe von n Zahlen, einem Nummer, die mehr als n/8 mal erscheint.

Jetzt habe ich die Antwort, die ist:

Wir werden an Orten, für die Zahlen Wählen Sie tun: n/9,2 * n/9,3 * n/9, ..., 8 * n/9, und dann prüfen, ob einer dieser 8 Kandidaten mindestens n/8 mal erscheint.

Aber ich verstehe nicht, warum dieser Algorithmus arbeiten würde. B. das folgende Array: [3,3,1,3,2,3,4,3,5,3,6,3,7,3,8,3,9,3] .

Also hier n = 18, und wenn für diesen Algorithmus die Kandidaten wären 1,2,4,5,6,7,8,9 und wenn wir überprüfen, ob diese Zahlen mindestens n/8 mal erscheinen Die Antwort wird nein sein, aber für 3 wäre die Antwort ja.

So verstehe ich nicht, warum dieser Algorithmus korrekt ist ...

Answer 1

Die wichtigste Erkenntnis dabei ist, dass Select, vor allem, wenn aktiviert, eine besondere Bedeutung hat: es verweist auf das Problem der Suche nach dem k-ten größte Eintrag in ein unsortiertes Array. Vielleicht etwas überraschend a priori kann dies in linearer Zeit erfolgen, zum Beispiel unter Verwendung einer Median-von-5-Pivotisierungsstrategie in Kombination mit dem QuickSelect-Algorithmus. Wenn Sie also die n/9, 2n/9, ... Einträge (Kosten: 9 * linear - was linear ist) Select-with-ein-Großbuchstaben-S auswählen, finden Sie definitiv alle Einträge, die n/8 mal vorkommen. Wiederholen Sie dann Ihr Array erneut, um die Anzahl der Vorkommen jedes dieser Kandidaten zu zählen, und seien Sie fertig.