Majority Element

Q: Was, wenn das Array möglicherweise kein Mehrheitselement enthält?

Boyer-Moore gibt immer einen Kandidaten zurück: Bei [1, 2, 3] gibt es 3 zurück. Füge einen zweiten Durchlauf hinzu, der den Kandidaten zählt, und akzeptiere ihn nur, wenn die Anzahl größer als n / 2 ist. Der Gesamtaufwand bleibt bei O(n) Zeit und O(1) Speicherplatz.

LeichtHashing

+10

Du erhältst ein Array aus Ganzzahlen nums der Länge n. Ein Wert kommt darin mehr als n / 2 Mal vor und wird als Mehrheits-Element bezeichnet. Gib ihn zurück. Ein Wert, der mehr als die Hälfte des Arrays ausfüllt, ist immer eindeutig, daher gibt es genau eine Antwort.

Funktion

majorityElement(nums: integer-array) → integer

numsinteger-array: das Array aus Ganzzahlen, in dem ein Wert mehr als die Hälfte der Elemente ausmacht
Gibt zurückinteger: der Wert, der mehr als n / 2 Mal vorkommt

Einschränkungen

1 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹
Ein Wert kommt mehr als nums.length / 2-mal vor.

Beispiele

Eingabe: nums = [3, 9, 3, 3, 4]
Ausgabe: 3
Erklärung: 3 kommt in fünf Elementen dreimal vor. Drei ist größer als 5 / 2 = 2.5, und 9 und 4 kommen jeweils einmal vor.

Weiterführende Frage

Kannst du jeden Wert finden, der mehr als n / 3 Mal vorkommt, in O(n) Zeit mit O(1) zusätzlichem Speicher?

Lösung

Der Mehrheitswert ist häufiger als alle anderen Werte zusammengenommen. Streiche Paare unterschiedlicher Werte durch, und einige seiner Vorkommen bleiben immer übrig. Der Boyer-Moore-Abstimmungsalgorithmus bildet diese Paare in einem Durchlauf mit einem Kandidaten und einem Zähler, sodass du keine Hash-Map mit Häufigkeiten benötigst.

Zählen mit einer Hash-Map

Idee

Zähle jeden Wert in einer Hashmap und gib den ersten Wert zurück, dessen Häufigkeit die Hälfte der Länge überschreitet. Für [3, 9, 3, 3, 4] erreicht die Häufigkeit von 3 bei Index 3 den Wert 3, also mehr als 2.5. Daher gibst du den Wert zurück, bevor du die 4 liest.

Jeder Suchvorgang benötigt durchschnittlich O(1), daher beträgt die Laufzeit O(n). Die Map kann jedoch etwa n / 2 verschiedene Werte enthalten: O(n) Speicherplatz.

Algorithmus

Erstelle eine leere Zuordnung von Werten zu Häufigkeiten.
Addiere für jedes Element x 1 zur Häufigkeit von x.
Wenn diese Häufigkeit multipliziert mit 2 größer als die Länge des Arrays ist, gib x zurück.

def majorityElement(nums):
    counts = {}
    for x in nums:
        counts[x] = counts.get(x, 0) + 1
        if counts[x] * 2 > len(nums):
            return x

Boyer-Moore-Abstimmungsverfahren

Idee

Führe einen candidate und einen count der noch nicht aufgehobenen Stimmen für ihn. Ein Element, das dem Kandidaten entspricht, fügt eine Stimme hinzu. Ein anderes Element hebt eine Stimme auf, und beide scheiden aus dem Rennen aus. Bei einem Zählerstand von 0 wird das nächste Element zum Kandidaten.

Jede Aufhebung entfernt zwei unterschiedliche Werte, darunter höchstens eine Kopie des Mehrheitswerts. Wenn der Mehrheitswert m-mal vorkommt, sind die übrigen n - m Elemente weniger als m und können nicht jede Kopie aufheben. Jede am Ende verbleibende Stimme gehört zum endgültigen Kandidaten, und eine Kopie des Mehrheitswerts ist darunter.

Bei [8, 8, 1, 1, 8, 1, 8] steigt der Zählerstand auf 1, 2, 1, 0, während die 1en beide 8en aufheben. Die nächste 8 setzt den Zählerstand auf 1 zurück, die nächste 1 hebt sie auf, und die letzte 8 wird wieder zum Kandidaten. Ein Durchlauf mit zwei Variablen benötigt O(n) Zeit und O(1) Speicher.

Algorithmus

Setze candidate auf das erste Element und count auf 0.
Für jedes Element x: Wenn count 0 ist, mache x zum Kandidaten.
Wenn x gleich dem Kandidaten ist, addiere 1 zu count. Andernfalls subtrahiere 1.
Gib nach dem letzten Element candidate zurück.

def majorityElement(nums):
    candidate = nums[0]
    count = 0
    for x in nums:
        if count == 0:
            candidate = x  # the old candidate's votes are used up
        if x == candidate:
            count += 1
        else:
            count -= 1  # x and one copy of the candidate cancel out
    return candidate

Stolperfallen und Grenzfälle

„Mehr als die Hälfte“ ist strikt. count >= n / 2 akzeptiert 2 Kopien von 4, was keine Mehrheit ist. Vergleiche count * 2 > n, dann kommt dir keine Rundung in die Quere.
Den abschließenden Wert von count als Häufigkeit des Mehrheitselements lesen. Bei [8, 8, 1, 1, 8, 1, 8] endet er bei 1, während 8 viermal vorkommt.
Mit candidate = nums[0] und count = 1 beginnen und dann ab Index 0 durchlaufen. Das erste Element stimmt zweimal ab: Bei [1, 2, 2] endet der Zähler bei 0 und du gibst 1 zurück.

Häufige Fragen3

Wie hoch sind die Zeit- und Speicherkomplexität des Mehrheitselements?

Die Boyer-Moore-Abstimmung läuft in O(n) Zeit und benötigt O(1) zusätzlichen Speicherplatz. Das Zählen mit einer Hash-Map benötigt ebenfalls O(n) Zeit, aber O(n) Speicherplatz für die Zählwerte. Das vorherige Sortieren benötigt O(n log n) Zeit.

Kann man das Problem des Mehrheitselements durch Sortieren lösen?

Ja. Nach dem Sortieren liegen alle Kopien des Mehrheitselements in einem Block, der länger als die Hälfte des Arrays ist, und jeder solche Block umfasst die mittlere Position. Daher ist das Element am Index n / 2, abgerundet, die Antwort. Der Zeitaufwand beträgt O(n log n).

Was, wenn das Array möglicherweise kein Mehrheitselement enthält?

Boyer-Moore gibt immer einen Kandidaten zurück: Bei [1, 2, 3] gibt es 3 zurück. Füge einen zweiten Durchlauf hinzu, der den Kandidaten zählt, und akzeptiere ihn nur, wenn die Anzahl größer als n / 2 ist. Der Gesamtaufwand bleibt bei O(n) Zeit und O(1) Speicherplatz.

def majorityElement(nums):
    # Schreibe hier den Code

Test #1

Test #2

Argument

nums = [3, 9, 3, 3, 4]

Erwartete Ausgabe