Häufigstes Element in einem Array / Die relative Mehrheit, deterministisch in O (n) Zeit und O (1) Raum finden?

Verwenden Sie die Idee von hier:

Wie können wir eine wiederholte Zahl im Array in O (n) Zeit und O (1) Raumkomplexität finden

Und wenden Sie eine ähnliche Methode wie counting sort an. Erstellen Sie also N Bins (ein Array der Größe N), wobei N die größte zu erwartende ganze Zahl ist. Dies ist immer noch O (1) Raum. Iterieren Sie dann das ursprüngliche Array in O (n) -Zeit, und wenn Sie auf einen Wert i stoßen, inkrementieren Sie das Ergebnisarray um den Index i um 1. Durchlaufen Sie anschließend iterativ das Ergebnisarray (wieder O (1) Zeit), wobei der größte Einzelwert gefunden wird. Der Index dieses Werts ist der häufigste Wert in der ursprünglichen Liste.

Dies ist keine vollständige Antwort, aber es sollte helfen, etwas Licht in die Frage zu bekommen, warum dieses Problem schwierig ist.

Denken Sie daran, wir wollen einen Algorithmus entwerfen, der das Array (in einer bestimmten Reihenfolge) überstreicht, um das am häufigsten verwendete Element zu finden. Während der Ausführung unseres Algorithmus ist es erlaubt, einige Datenstrukturen S zu behalten. Lassen Sie uns sehen, wie viele Informationen in S vorhanden sein müssen, und daher können wir sie in O(1) memory enthalten.

Nehmen wir an, unser Algorithmus hat die ersten k -Elemente des Arrays verarbeitet. Jetzt kann S uns das häufigste Element im Bereich a[0..k] mitteilen. Wenn wir jedoch das Element k+1 'st kennen, dann kennen wir auch das häufigste Element im Bereich a[0..k+1] . Wenn dies nicht möglich wäre, würde unser Algorithmus nicht funktionieren, wenn n k+1 wäre. Allgemeiner gesagt, bei Kenntnis der Elemente a[k..m] und S kennen wir das häufigste Element in a[0..m] .

Wir können das obige Argument verwenden, um Informationen aus S zu extrahieren. Angenommen, wir arbeiten mit Ganzzahlen im Bereich [0,u] (es muss ein Bereich vorhanden sein, wenn das ursprüngliche Array Platz O(n) benötigte). Wenn das ursprünglichste Element 5 ist, fügen wir 0 's hinzu, bis sich das häufigste Element ändert. Wenn das c Nullen benötigt, muss a[0..k] c mehr 5 enthalten als 0 . Wenn wir dieses Argument wiederholen, erhalten wir viele lineare Gleichungen, die wir lösen können, um genau zu bestimmen, wie oft jedes der Elemente [0,u] in a[0..k] vorhanden war.

Dies sagt uns, dass jede Datenstruktur, die einen Sweep ausführt, auch die Zählungen aller gesehenen Elemente (in einer komprimierten Weise) speichern könnte. Wenn Sie sich für die Mathematik interessieren, wird nach dem Anzeigen von n numbers log(n+u-1 choose n) gespeichert. Dies ist das Protokoll der Anzahl der Möglichkeiten, n nicht unterscheidbare Elemente in u unterscheidbare Klassen zu partitionieren. Das ist mehr als log(u^n/n!) >= nlogu-nlogn .

Schlussfolgerung : Jeder Algorithmus, der nur einen Durchlauf des Arrays durchführt, muss so viel Speicher belegen, wie er benötigt, um alle bisher gesehenen Zählungen zu speichern. Wenn n klein im Vergleich zu u ist, entspricht dies dem Speichern von n Wörtern des Speichers.

(Nun, anstelle von zusätzlichem Speicher können wir auch das vorhandene Array überschreiben).

Hier gibt es viel mehr zu entdecken. Z.B. wie mehrere Durchgänge die obigen Argumente beeinflussen. Aber ich denke, ich sollte an dieser Stelle aufhören :), aber es scheint mir nicht wahrscheinlich, dass irgendein linearer Zeitalgorithmus mit einem großen u mit O(1) extra Speicher davonkommen kann.

Wenn Sie einen festen Platz haben möchten, um das am häufigsten verwendete Element zu finden, benötigen Sie eine maximale Anzahl von Bits für ein Element. Wenn dies nicht der Fall ist, können große Eingabearrays größere Eingabezahlen haben, so dass die Bits, die die Zahl darstellen, größer als Ihr fester Speicherplatz zum Speichern des Ergebnisses sind.

Angenommen, k ist die Länge der größten Zahl, die Sie unterstützen. Wenn Sie versuchen, naiv ein Array von 2^k Buckets zu erstellen, um die Vorkommen jeder Zahl zu zählen (Counter sort), könnten Sie ein Array mit derselben Nummer erhalten. In diesem Fall würde Ihr Algorithmus log(n) space zum Speichern der Summe. [*]

Wenn wir uns eine einfachere Version des Problems ansehen - ob es mehr 1 's oder 0 ' s in einer Eingabe gibt, denke ich, dass Sie dafür einen Stack benötigen (Sie speichern wie viel 1 oder 0 führt nach), und so ist konstanter Speicherplatz nicht möglich, selbst wenn wir die Eingabelänge auf k = 1 in der Größe begrenzen.

Ihr Problem ist allgemeiner ( k > 1 , aber immer noch behoben), und würde auch nicht-konstanten Raum brauchen, also ist es nicht möglich, wie die Frage formuliert ist.

[*] Wenn Sie annehmen, dass Counter die O(1) -Komplexität haben, dann können Sie den Counter-Sort-Ansatz wählen, obwohl Sie damit eine Obergrenze für die maximale Größe Ihres Eingabe-Arrays gesetzt haben möglicherweise nicht akzeptabel): In k , die maximale Anzahl von Bits für ein Eingabeelement Ihres Arrays und in c die maximale Anzahl von Bits in Ihrem Zähler kann Ihr Array höchstens 2^k * 2^c elements haben (Einer der Zähler würde andernfalls beim nächsten Element überlaufen). Um dies zu beheben, könnten Sie einen O(1) -Zeitschritt hinzufügen, um Ihre Zähler so zu dekrementieren, dass der Mindestwert immer 0 ist, nachdem jedes Element verarbeitet wurde, wenn alle Zähler nicht 0 sind. Dies dauert O(1) time, denn wenn alle Werte ungleich Null sind, müssen Sie O(2^k) = O(1) counters um 1 nur dekrementieren, wenn Sie sie für jedes Element ausführen. Während der Algorithmus nun einige beliebig große Eingaben verarbeiten kann, wird jedes Eingabe-Array, das ein Unter-Array hat, so dass die beiden Werte a und b so ausfallen, dass count(a) - count(b) > 2^c = max(counter) bei Verwendung einer Counter-Strategie für einige Eingaben fehlschlägt. In der Tat ist es eine Konsequenz davon, sich auf einen O(1) -Raumkomplexitätszähler-Ansatz zu verlassen, dass alle Arrays, die mit 2^c + 1 identischen Elementen beginnen, von diesem Algorithmus nicht behandelt werden können.

Dies ist mein Skript, um das am häufigsten verwendete Element in einem Array zu lesen