Majority Element

+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 Mehrheitswert 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, wobei ein Wert mehr als die Hälfte davon ausfüllt
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 mehr als 5 / 2 = 2.5, und 9 sowie 4 kommen jeweils einmal vor.

+15 versteckte Tests beim Einreichen

Weiterführende Frage

Kannst du das Mehrheitselement in O(n)-Zeit mit O(1) zusätzlichem Speicher finden, ohne das Array zu sortieren?

Lösung

Zu zählen, wie oft jeder Wert vorkommt, beantwortet die Frage, aber dafür braucht man eine Hash-Map. Um darauf zu verzichten, muss man erkennen, was den Mehrheitswert besonders macht: Er kommt häufiger vor als alle anderen Werte zusammen. Paart man jede Kopie dieses Werts mit einem anderen Wert und streicht beide durch, bleiben immer einige Kopien übrig. Beim Boyer-Moore-Mehrheitsvotum werden diese Paare in einem Durchlauf mit einem Kandidaten und einem Zähler gebildet.

Mit einer Hash-Map zählen

Idee

Durchlaufe das Array und führe eine Hash-Map, die jeden Wert der Anzahl seiner bisherigen Vorkommen zuordnet. Nachdem du den Zähler eines Werts um eins erhöht hast, prüfe, ob dieser Zähler jetzt größer als die Hälfte der Länge ist. Der erste Wert, der diese Grenze überschreitet, ist das Mehrheitselement, also kannst du ihn sofort zurückgeben.

Für [3, 9, 3, 3, 4] wird der Zähler von 3 an Index 0 zu 1, an Index 2 zu 2 und an Index 3 zu 3. Drei Vorkommen von fünf sind mehr als 2.5, also gibst du 3 zurück, ohne das letzte Element zu lesen.

Eine Abfrage und Aktualisierung in einer Hash-Map dauern im Durchschnitt O(1), daher beträgt die Laufzeit O(n). Die Map kann bis zu etwa n / 2 verschiedene Werte enthalten, daher beträgt der zusätzliche Speicherbedarf O(n). Der nächste Ansatz kommt ohne die Map aus.

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 mal 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-Abstimmung

Idee

Betrachte das Array als Wahl. Behalte einen candidate und einen count seiner Stimmen, die noch von nichts aufgehoben wurden. Ein Element, das dem Kandidaten entspricht, fügt eine Stimme hinzu. Ein abweichendes Element hebt eine Stimme auf, und beide scheiden gemeinsam aus dem Rennen aus. Wenn der Zähler 0 ist, wird das nächste Element zum neuen Kandidaten.

Warum der am Ende übrig bleibende Wert die Mehrheit ist: Jede Aufhebung entfernt zwei verschiedene Werte und damit höchstens eine Kopie des Mehrheitswerts. Angenommen, der Mehrheitswert kommt m-mal vor. Es gibt nur n - m andere Elemente, also weniger als m; sie können daher nicht alle Kopien aufheben. Jede Stimme, die am Ende noch steht, gehört zum endgültigen Kandidaten, und eine Kopie des Mehrheitswerts ist darunter. Also ist der Kandidat der Mehrheitswert.

Bei [8, 8, 1, 1, 8, 1, 8] lautet der Zählerstand 1, 2, 1, 0: Die beiden 1en haben beide 8en aufgehoben. Die nächste 8 beginnt erneut mit einem Zählerstand von 1, die nächste 1 hebt sie auf, und die letzte 8 wird wieder zum Kandidaten. Du gibst 8 zurück. 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.
Wenn count 0 ist, setze für jedes Element x x als Kandidaten.
Wenn x dem Kandidaten entspricht, 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

Die meisten falschen Antworten entstehen an der Grenze zur Hälfte oder dadurch, dass zu viel in den Zähler hineininterpretiert wird.

„Mehr als die Hälfte“ bedeutet strikt mehr. count >= n / 2 akzeptiert 2 Vorkommen von 4, was keine Mehrheit ist. Vergleiche count * 2 > n; so kann keine Rundung dazwischenkommen.
Der abschließende count bei Boyer-Moore gibt nicht an, wie oft die Mehrheit vorkommt. Bei [8, 8, 1, 1, 8, 1, 8] endet er bei 1, während 8 viermal vorkommt.
Mit candidate = nums[0] und count = 1 zu beginnen, funktioniert nur, wenn die Schleife dann bei Index 1 startet. Beginnt sie bei Index 0, stimmt das erste Element zweimal ab: Bei [1, 2, 2] endet der Zähler bei 0 und du gibst 1 zurück.
Boyer-Moore setzt die Garantie voraus. Bei [1, 2, 3], wo es keine Mehrheit gibt, gibt der Algorithmus trotzdem 3 zurück. Wenn eine Eingabe möglicherweise keine Mehrheit enthält, zähle den Kandidaten in einem zweiten Durchlauf, bevor du ihm vertraust.

Häufige Fragen4

Was ist der Boyer-Moore-Mehrheitsalgorithmus?

Es findet den Wert, der mehr als die Hälfte einer Liste ausmacht, in einem Durchlauf mit O(1) Speicher. Es verwaltet einen Kandidaten und einen Zähler: Ein übereinstimmendes Element erhöht den Zähler um eins, ein anderes Element verringert ihn um eins, und bei 0 wird das nächste Element zum Kandidaten. Da die Mehrheit alle anderen Werte zusammen zahlenmäßig übertrifft, bleibt sie am Ende als Kandidat übrig.

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

Das Boyer-Moore-Voting-Verfahren benötigt O(n) Zeit und O(1) zusätzlichen Speicherplatz. Das Zählen mit einer Hashmap benötigt ebenfalls O(n) Zeit, aber O(n) Speicherplatz für die Zählwerte. Vorheriges Sortieren benötigt O(n log n) Zeit.

Kann das Problem des Mehrheitselements durch Sortieren gelöst werden?

Ja. Nach dem Sortieren liegen alle Kopien des Mehrheitswerts in einem zusammenhängenden Block, der länger als die Hälfte des Arrays ist, und jeder solche Block umfasst die mittlere Position. Das Element am Index n / 2, abgerundet, ist also die Antwort. Das ist kurz zu schreiben, kostet aber O(n log n) Zeit.

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

Boyer-Moore gibt immer einen Kandidaten zurück, selbst wenn kein Wert mehr als die Hälfte des Arrays ausfüllt. 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.

Python

def majorityElement(nums):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Eingabe

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

Erwartet