Finden Sie die häufigste Eintrag in einem Array

Question

Sie sind Array 32-bit unsignierte Ganzzahl gegeben mit einer Länge von bis zu 2 ³² , mit der Eigenschaft, daß mehr als die Hälfte der Einträge in dem Array N gleich sind, für einige 32-bit unsigned integer N. nur einmal in jeder Reihe in dem Array Finden N suchen und höchstens 2 kB Speicher.

Ihre Lösung muss deterministisch sein, und garantiert N finden.

Answer 1

Halten eine ganze Zahl für jedes Bit, und inkrementiert diese Sammlung entsprechend für jede ganze Zahl in dem Array.

Am Ende einige der Bits wird die Länge des Arrays eine Zählung höher als die Hälfte haben - diese Bits bestimmen N. Natürlich wird der Zählwert höher sein als die Anzahl N aufgetreten, aber das bedeutet nicht Angelegenheit. Das Wichtigste ist, dass jedes Bit, das nicht Teil der N ist nicht auftritt mehr als die Hälfte der Zeit (weil N die Hälfte über die Einträge hat) und ein Bit, das muss ist / em> auftritt mehr als die Hälfte der Zeit (weil es jedes Mal, N auftritt, und alle Extras auftreten wird).

(kein Code zur Zeit -.. Über den Netzzugang verlieren Hoffentlich wird die oben klar genug ist, obwohl)

Answer 2

Boyer und Moores "Linear Time Majority Vote Algorithm" - gehen Sie die Array Ihre aktuelle Vermutung auf die Antwort erhalten.

Answer 3

Sie können dies tun, mit nur zwei Variablen.

public uint MostCommon(UInt32[] numberList)
{
    uint suspect = 0;
    int suspicionStrength = -1; 
    foreach (uint number in numberList)
    {
        if (number==suspect)
        {
            suspicionStrength++;
        }
        else
        {
            suspicionStrength--;
        }

        if (suspicionStrength<=0)
        {
            suspect = number;
        }
    }
    return suspect;
}

Machen Sie die erste Zahl der Verdächtige Nummer, und weiter durch die Liste Looping. Wenn die Zahl übereinstimmt, erhöhen Sie den Verdacht Stärke nach dem anderen; wenn dies nicht der Fall, durch eine den Verdacht Stärke senken. Wenn der Verdacht Stärke 0 trifft die aktuelle Zahl wird der Verdächtige Nummer. Dies wird nicht Arbeit die häufigste Zahl zu finden, die nur eine Zahl, die mehr als 50% der Gruppe ist. Den Drang wider einen Scheck hinzufügen, wenn suspicionStrength größer als die Hälfte der Listenlänge -. Es wird immer mehr Gesamt Vergleiche führt

P. S. Ich habe diesen Code nicht getestet -. Verwenden Sie es auf eigene Gefahr

Answer 4

Pseudo-Code (Notepad C ++ :-)) für Jon-Algorithmus:

int lNumbers = (size_of(arrNumbers)/size_of(arrNumbers[0]);

for (int i = 0; i < lNumbers; i++)
  for (int bi = 0; bi < 32; bi++)
    arrBits[i] = arrBits[i] + (arrNumbers[i] & (1 << bi)) == (1 << bi) ? 1 : 0;

int N = 0;

for (int bc = 0; bc < 32; bc++)
  if (arrBits[bc] > lNumbers/2)
    N = N | (1 << bc);

Answer 5

Beachten Sie, dass, wenn die Sequenz a0, a1, . . . , an−1 enthält einen Führer, dann nach einem Paar zu entfernen Elemente der verschiedenen Werte, hat die verbleibende Sequenz noch den gleichen Führer. Wenn wir nämlich entfernen dann zwei verschiedene Elemente nur einer von ihnen der Anführer sein könnte. Der Marktführer im Bereich der neue Sequenz tritt auf mehr als n/2 − 1 = (n−2)/2 mal. Folglich ist es immer noch der Führer der neue Folge von n − 2 Elementen.

Hier ist eine Python-Implementierung, mit O (n) Zeitkomplexität:

def goldenLeader(A):
    n = len(A)
    size = 0
    for k in xrange(n):
        if (size == 0):
            size += 1
            value = A[k]
        else:
            if (value != A[k]):
                size -= 1
            else:
                size += 1
    candidate = -1
    if (size > 0):
        candidate = value
    leader = -1
    count = 0
    for k in xrange(n):
        if (A[k] == candidate):
            count += 1
    if (count > n // 2):
        leader = candidate
    return leader

Answer 6

Dies ist ein Standardproblem in Streaming-Algorithmen (wo Sie haben einen riesigen (potentiell unendlichen) Strom von Daten) und Sie haben einige Statistiken aus diesem Strom zu berechnen, einmal durch diesen Strom übergeben.

---

Selbstverständlich können Sie es mit Hashing-Ansatz oder Sortierung, aber mit potenziell unendlichen Strom führen Sie klar aus dem Speicher. So haben Sie etwas Kluges zu tun.

---

Die Mehrheit Element ist das Element, das mehr als die Hälfte der Größe des Arrays auftritt. Das bedeutet, dass die Mehrheit Element mehr auftritt als alle anderen Elemente kombiniert oder wenn Sie die Anzahl der Male zählt, Mehrheits Element angezeigt wird, und die Anzahl aller anderen Elemente subtrahieren, erhalten Sie eine positive Zahl bekommen.

Wenn Sie also die Anzahl der ein Element zählen, und die Anzahl aller anderen Elemente subtrahieren und die Nummer 0 erhalten - dann Ihr ursprüngliches Element kann nicht eine Mehrheit Element sein. Dies, wenn die Grundlage für einen korrekten Algorithmus:

hat zwei Variablen, Zähler und mögliches Element. Iterate den Strom, wenn der Zähler 0 - Ihr überschreiben die mögliche Element und initialisieren Sie den Zähler, wenn die Zahl der gleiche wie möglich Element - den Zähler erhöhen, ist es sonst verringern Python-Code.

def majority_element(arr):
    counter, possible_element = 0, None
    for i in arr:
        if counter == 0:
            possible_element, counter = i, 1
        elif i == possible_element:
            counter += 1
        else:
            counter -= 1

    return possible_element

Es ist klar zu sehen, dass der Algorithmus O(n) mit einem sehr kleinen Konstante vor O(n) ist (wie 3). Auch sieht es aus wie der Raum Komplexität O(1) ist, weil wir nur drei Variable initialisiert haben. Das Problem ist, dass eine dieser Variablen ist ein Zähler, der auf n potentiell aufzuwachsen (wenn die Anordnung aus den gleichen Zahlen besteht). Und die Nummer zu speichern n Sie O(log (n)) Platz benötigen. So aus theoretischer Sicht ist O(n) Zeit und O(log(n)) Raum. Aus praktischen können Sie passen 2 ^ 128-Nummer in einem longint und diese Anzahl von Elementen in der Array unimaginably riesig ist.

Beachten Sie auch, dass der Algorithmus funktioniert nur, wenn es eine Mehrheit Element ist. Wenn ein solches Element nicht existiert es wird noch einige Nummer zurück, was sicherlich falsch sein wird. (Es ist leicht, den Algorithmus zu modifizieren, zu sagen, ob die Mehrheit Element vorhanden)

History Channel: Dieser Algorithmus wurde 1982 von Boyer, Moore irgendwo erfunden und nannte Boyer-Moore Stimmenmehrheit Algorithmus .

Answer 7

Ich habe Erinnerungen an diesem Algorithmus, der könnte oder der 2K Regel nicht folgen. Es müssen möglicherweise mit Stapeln neu geschrieben werden und dergleichen aufgrund Funktionsaufrufe brechen die Speichergrenzen zu vermeiden, aber dies könnte nicht benötigt werden, da es immer nur eine logarithmische Zahl solcher Anrufe hat. Wie auch immer, ich habe vage Erinnerungen aus dem College oder einer rekursiven Lösung dieses Problems, die Kluft beteiligt und erobern, das Geheimnis ist, dass, wenn Sie die Gruppen in zwei Hälften teilen, zumindest eine der Hälften noch mehr als die Hälfte der Werte gleich der max hat . Die Grundregel, wenn Teilung ist, dass Sie zwei in Frage kommende Top-Werte zurückgeben, einer davon ist der Spitzenwert und einer davon ist ein anderer Wert (das kann oder nicht Platz 2 sein kann). Ich vergesse den Algorithmus selbst.

Answer 8

Der Nachweis der Richtigkeit für Buti-Oxa / Jason Hernandez Antwort, Jasons Antwort unter der Annahme, ist die gleiche wie Buti-Oxa Antwort und beide arbeiten die Art und Weise sollte der beschriebene Algorithmus arbeiten:

Wir definieren eingestellt Verdacht Stärke als gleich zu sein, wenn Verdacht Festigkeit oberer Wert gewählt wird, oder wenn -suspicion Stärke oberer Wert nicht ausgewählt ist. Jedes Mal, wenn Sie die richtige Nummer zu wählen, die aktuellen eingestellten Verdacht Stärke erhöht sich um 1. Jedes Mal, wenn Sie eine falsche Nummer wählen, entweder sinkt um 1 oder um 1 erhöht, je nachdem, ob die falsche Nummer gerade ausgewählt ist. So ist die minimal mögliche Ende eingestellt Verdacht Stärke gleich zahlen von [Top-Werte] - Nummer-of [andere Werte]