Majority Element: Boyer-Moore-Abstimmung
Finden Sie mit dem linearen Boyer-Moore-Abstimmungsalgorithmus mit O(1) Speicher das Element, das mehr als n/2-mal vorkommt, und beweisen Sie dessen Korrektheit.
Majority Element: Boyer-Moore-Abstimmung ist eine kostenlose DSA Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 3 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des DSA Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Das Problem des Mehrheitselements
Majority Element (LeetCode 169): Finden Sie das Element, das in einem Array der Länge n mehr als n/2-mal vorkommt. Aufgrund der Vorgabe des Problems existiert das Mehrheitselement immer. Für [3, 2, 3] lautet die Antwort 3. Für [2, 2, 1, 1, 1, 2, 2] lautet die Antwort 2 (es kommt 4-mal bei insgesamt 7 Elementen vor). Die Ansätze reichen vom Sortieren in O(n log n) bis zum eleganten Boyer-Moore-Abstimmungsalgorithmus mit O(n) Laufzeit und O(1) Speicherbedarf.
# The majority element appears MORE than n/2 times
# So it appears more than all other elements COMBINED
examples = [
[3, 2, 3], # 3 appears 2/3 times > 1/2
[2, 2, 1, 1, 1, 2, 2], # 2 appears 4/7 times > 3.5
[1], # trivially 1
[1, 1, 2, 1], # 1 appears 3/4 times
]
for e in examples:
from collections import Counter
c = Counter(e)
print(f'Array: {e} → majority: {max(c, key=c.get)} (count {max(c.values())})')Ansätze vor Boyer-Moore
Drei Ansätze vor der optimalen Lösung: (1) Sortieren: Sortieren Sie das Array; das mittlere Element ist immer das Mehrheitselement (da es mehr als >n/2-mal vorkommt). O(n log n), O(1) Speicherbedarf. (2) Hash-Map: Zählen Sie die Häufigkeiten und geben Sie das Element mit einer Häufigkeit von > n/2 zurück. O(n) Zeit, O(n) Speicherbedarf. (3) Zufallsstichprobe: Wählen Sie ein zufälliges Element aus und überprüfen Sie, ob es mehr als >n/2-mal vorkommt; im Erwartungswert sind O(1) Versuche nötig (das Mehrheitselement wird mit einer Wahrscheinlichkeit von >1/2 ausgewählt). Boyer-Moore erreicht deterministisch O(n) Zeit und O(1) Speicherbedarf.
from collections import Counter
def majority_sort(nums):
nums.sort()
return nums[len(nums) // 2] # middle is always majority
def majority_hashmap(nums):
count = Counter(nums)
return max(count, key=count.get)
def majority_random(nums):
import random
n = len(nums)
while True:
candidate = random.choice(nums)
if nums.count(candidate) > n // 2:
return candidate
nums = [2, 2, 1, 1, 1, 2, 2]
print(majority_sort(nums[:])) # 2
print(majority_hashmap(nums)) # 2Boyer-Moore-Abstimmungsalgorithmus
Der Boyer-Moore-Abstimmungsalgorithmus verwaltet einen candidate und einen count. Durchlaufen Sie das Array: Falls count == 0 gilt, setzen Sie das aktuelle Element als neuen Kandidaten. Stimmt das aktuelle Element mit dem Kandidaten überein, erhöhen Sie count. Andernfalls verringern Sie count. Am Ende ist der Kandidat das Mehrheitselement. Das funktioniert, weil das Mehrheitselement häufiger vorkommt als alle anderen Elemente zusammen – es kann niemals vollständig herausgewählt werden.
def majority_element(nums):
candidate = None
count = 0
for num in nums:
if count == 0:
candidate = num # new candidate
if num == candidate:
count += 1
else:
count -= 1
return candidate
print(majority_element([3, 2, 3])) # 3
print(majority_element([2, 2, 1, 1, 1, 2, 2])) # 2
print(majority_element([1])) # 1Intuition hinter dem Algorithmus
Die Idee dahinter: Stellen Sie sich vor, dass jedes Element ein Vorkommen eines anderen Elements „aufhebt“. Das Mehrheitselement (count > n/2) kommt häufiger vor als alle anderen Elemente zusammen, kann also alle Nicht-Mehrheitselemente aufheben und hat danach noch Vorkommen übrig. Die Variable count verfolgt den Netto-Vorsprung des aktuellen Kandidaten. Wenn count den Wert 0 erreicht, wurde der aktuelle Kandidat durch ebenso viele gegnerische Elemente aufgehoben – das nächste auftretende Element wird zum neuen Kandidaten.
def bm_trace(nums):
candidate = count = 0
for i, num in enumerate(nums):
if count == 0:
candidate = num
old_count = count
if num == candidate: count += 1
else: count -= 1
print(f'num={num}: candidate={candidate}, count: {old_count}→{count}')
return candidate
bm_trace([2, 2, 1, 1, 1, 2, 2])
# 2→c=1, 2→c=2, 1→c=1, 1→c=0, 1→new cand=1 c=1, 2→c=0, 2→new cand=2 c=1Korrektheitsbeweis
Beweis: Sei m das Mehrheitselement mit count k > n/2. Kann am Ende des Algorithmus ein Nicht-Mehrheitselement der Kandidat sein? Dafür müsste m vollständig aufgehoben worden sein. Jede Aufhebung von m kostet ein Vorkommen eines anderen Elements. Um alle k Vorkommen von m aufzuheben, benötigt man mindestens k Vorkommen von Nicht-m-Elementen. Doch die Nicht-m-Elemente umfassen insgesamt n-k < n/2 < k Vorkommen. Widerspruch – m kann nicht vollständig aufgehoben werden.
# Proof by contradiction visualised:
# Array: [M, M, M, A, B, A, B] (M is majority, 4/7 times)
# Cancellations: M-A, M-B, M-A, M-B would need 4 non-M elements
# But there are only 4 non-M elements and 4 M's > n/2 = 3.5
# So M can survive: after cancellations, at least 1 M remains uncancelled
def verify_bm(tests):
for nums in tests:
result = majority_element(nums)
brute = max(set(nums), key=nums.count)
assert result == brute, f'Mismatch: {nums} → BM={result}, Brute={brute}'
print('All tests passed!')
def majority_element(nums):
c = cnt = 0
for n in nums:
if cnt == 0: c = n
cnt += 1 if n == c else -1
return c
verify_bm([[1],[3,2,3],[1,1,2,1],[2,2,1,1,1,2,2]])Mehrheitselement II: Mehr als n/3
Majority Element II (LeetCode 229): Finden Sie alle Elemente, die mehr als n/3-mal vorkommen. Höchstens 2 Elemente können diese Bedingung erfüllen (denn 3 × n/3 = n). Erweitern Sie Boyer-Moore, indem Sie zwei Kandidaten mit zwei Zählern verwalten. Wenn ein neues Element zu keinem der beiden Kandidaten passt und beide Zähler positiv sind, verringern Sie beide. Ein abschließender Verifikationsdurchlauf bestätigt, welche Kandidaten tatsächlich häufiger als n/3 vorkommen.
def majority_element_ii(nums):
cand1 = cand2 = None
count1 = count2 = 0
for num in nums:
if num == cand1: count1 += 1
elif num == cand2: count2 += 1
elif count1 == 0: cand1, count1 = num, 1
elif count2 == 0: cand2, count2 = num, 1
else:
count1 -= 1
count2 -= 1
# Verify: candidates must exceed n/3
n = len(nums)
return [c for c in [cand1, cand2]
if c is not None and nums.count(c) > n // 3]
print(majority_element_ii([3, 2, 3])) # [3]
print(majority_element_ii([1, 2])) # [1, 2]
print(majority_element_ii([1, 1, 1, 3, 3, 2, 2, 2])) # [1, 2]Verallgemeinerter Boyer-Moore: Mehrheit mit n/k
Boyer-Moore lässt sich verallgemeinern, um alle Elemente zu finden, die häufiger als n/k-mal vorkommen, indem k-1 Kandidaten verwendet werden. Höchstens k-1 Elemente können diese Bedingung erfüllen. Verwalten Sie k-1 Paare aus (Kandidat, Zähler). Wenn kein Kandidat übereinstimmt und alle Zähler positiv sind, verringern Sie alle Zähler um 1. Dieser verallgemeinerte Algorithmus läuft in O(n) Zeit und benötigt O(k) Speicher. In Vorstellungsgesprächen reicht es normalerweise aus, die Erweiterung mit zwei Kandidaten für n/3 zu kennen.
def majority_nk(nums, k):
'''Find all elements appearing more than n/k times.'''
counts = {} # candidate -> count
for num in nums:
counts[num] = counts.get(num, 0) + 1
if len(counts) >= k:
# Remove all candidates by decrementing
new_counts = {c: cnt-1 for c, cnt in counts.items() if cnt > 1}
counts = new_counts
# Verify
threshold = len(nums) // k
return [c for c in counts if nums.count(c) > threshold]
print(majority_nk([1,2,3,1,2,1,2,1], 3)) # [1, 2] (both > 8/3 ≈ 2.67)
print(majority_nk([1,1,1,2,2,3,3,3], 4)) # [1, 3] (both > 8/4 = 2)Mehrheitselement mit Teile und Herrsche
Ein Teile-und-herrsche-Ansatz: Teilen Sie das Array in zwei Hälften. Das Mehrheitselement des gesamten Arrays muss in mindestens einer Hälfte ein Mehrheitselement sein (wenn es in keiner Hälfte die Mehrheit hätte, könnte es insgesamt nicht mehr als n/2-mal vorkommen). Finden Sie rekursiv das Mehrheitselement jeder Hälfte. Stimmen beide Hälften überein, ist dies die Antwort. Andernfalls zählen Sie beide Kandidaten im gesamten Array und geben Sie denjenigen mit den meisten Vorkommen zurück. Rekurrenz: T(n) = 2T(n/2) + O(n) → O(n log n).
def majority_dc(nums, lo=None, hi=None):
if lo is None: lo, hi = 0, len(nums) - 1
if lo == hi: return nums[lo]
mid = (lo + hi) // 2
left_maj = majority_dc(nums, lo, mid)
right_maj = majority_dc(nums, mid + 1, hi)
if left_maj == right_maj:
return left_maj
# Count both candidates across the sub-range
left_count = sum(1 for i in range(lo, hi+1) if nums[i] == left_maj)
right_count = sum(1 for i in range(lo, hi+1) if nums[i] == right_maj)
return left_maj if left_count > right_count else right_maj
print(majority_dc([3, 2, 3])) # 3
print(majority_dc([2, 2, 1, 1, 1, 2, 2])) # 2Boyer-Moore im Vergleich zu anderen Verfahren
Vergleich der Verfahren für Majority Element: Sortieren: O(n log n) Zeit, O(1) Speicherbedarf, destruktiv. Hash-Map: O(n) Zeit, O(n) Speicherbedarf, nicht destruktiv. Teile und Herrsche: O(n log n) Zeit, O(log n) Speicherbedarf für den Aufruf-Stack. Boyer-Moore: O(n) Zeit, O(1) Speicherbedarf, ein einziger Durchlauf, nicht destruktiv. Boyer-Moore ist für dieses Problem eindeutig überlegen. Stellen Sie in Vorstellungsgesprächen nach einer kurzen Erwähnung des einfacheren Hash-Map-Ansatzes immer zuerst Boyer-Moore vor.
import time, random
nums = [random.randint(1, 100) for _ in range(500000)]
# Make element 42 the majority
nums = [42] * 300000 + nums[:200000]
random.shuffle(nums)
start = time.time()
from collections import Counter
hm = Counter(nums).most_common(1)[0][0]
print(f'HashMap: {hm} in {time.time()-start:.4f}s')
def bm(nums):
c = cnt = 0
for n in nums:
if cnt == 0: c = n
cnt += 1 if n == c else -1
return c
start = time.time()
result = bm(nums)
print(f'Boyer-Moore: {result} in {time.time()-start:.4f}s')
print(f'Both correct: {hm == result}')Wenn keine Mehrheit garantiert ist
Boyer-Moore gibt immer einen Kandidaten zurück, doch dieser ist möglicherweise kein Mehrheitselement, wenn keines existiert. Falls das Problem kein Mehrheitselement garantiert, müssen Sie eine Überprüfung durchführen: Zählen Sie nach Boyer-Moore die Vorkommen des Kandidaten. Wenn count > n/2 gilt, ist er das Mehrheitselement. Andernfalls geben Sie -1 oder None zurück. Diese Überprüfung fügt einen weiteren Durchlauf mit O(n) hinzu, aber der Gesamtalgorithmus bleibt bei O(n) Zeit und O(1) Speicherbedarf.
def majority_element_safe(nums):
'''Returns majority element or None if it doesn't exist.'''
# Phase 1: find candidate
candidate = count = 0
for num in nums:
if count == 0:
candidate = num
count += 1 if num == candidate else -1
# Phase 2: verify
if nums.count(candidate) > len(nums) // 2:
return candidate
return None
print(majority_element_safe([3, 2, 3])) # 3 (majority exists)
print(majority_element_safe([1, 2, 3])) # None (no majority)
print(majority_element_safe([1, 2, 1, 2])) # None (tie, neither > n/2)Vorgehensweise im Vorstellungsgespräch
Vorgehensweise für Majority Element im Vorstellungsgespräch: (1) Nennen Sie Sortieren (O(n log n), O(1)) und eine Hash-Map (O(n), O(n)) als erste Ansätze. (2) Führen Sie Boyer-Moore als optimale Lösung mit O(n) und O(1) ein. (3) Erklären Sie die Aufhebungsintuition: Das Mehrheitselement kann nicht vollständig aufgehoben werden, weil es häufiger vorkommt als alle anderen Elemente zusammen. (4) Implementieren Sie den Algorithmus sauber in 5 Zeilen. (5) Behandeln Sie den Sonderfall: Wenn die Mehrheit nicht garantiert ist, fügen Sie einen Verifikationsdurchlauf hinzu. Diese Struktur zeigt systematisches Denken unter Zeitdruck.
# Clean 5-line Boyer-Moore for interviews
def majority_element(nums):
c, cnt = nums[0], 1
for n in nums[1:]:
cnt += (1 if n == c else -1)
if cnt == 0: c, cnt = n, 1
return c
# Verification (if majority not guaranteed)
def majority_with_check(nums):
c = majority_element(nums)
return c if nums.count(c) > len(nums) // 2 else -1
print(majority_element([3, 2, 3])) # 3
print(majority_element([2, 2, 1, 1, 1, 2, 2])) # 2
print('Time: O(n), Space: O(1)')Schnelltest
Überprüfen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep, die in dieser Lektion behandelt wurden.
Zusammenfassung der Lektion
In dieser Lektion haben Sie gelernt: Die Boyer-Moore-Abstimmung findet das Mehrheitselement in O(n) Zeit und mit O(1) Speicherbedarf, indem ein Kandidat und ein Zähler Nicht-Mehrheitselemente gegenseitig aufheben, der Algorithmus lässt sich mit zwei Kandidaten auf eine Mehrheit von n/3 erweitern und benötigt einen Verifikationsdurchlauf, wenn keine Mehrheit garantiert ist, und der Beweis beruht auf der Tatsache, dass das Mehrheitselement häufiger vorkommt als alle anderen Elemente zusammen, wodurch eine vollständige Aufhebung unmöglich ist. Als Nächstes befassen wir uns mit dem Median zweier sortierter Arrays und verwenden dazu eine binäre Suche über die Partitionsgrenze.
Häufig gestellte Fragen
Ist die Lektion „Majority Element: Boyer-Moore-Abstimmung“ kostenlos?
Ja — der vollständige Text von „Majority Element: Boyer-Moore-Abstimmung“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des DSA Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Majority Element: Boyer-Moore-Abstimmung“?
Finden Sie mit dem linearen Boyer-Moore-Abstimmungsalgorithmus mit O(1) Speicher das Element, das mehr als n/2-mal vorkommt, und beweisen Sie dessen Korrektheit. Du übst DSA Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um DSA Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. DSA Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 3 von 4.
Wie lange dauert die Lektion „Majority Element: Boyer-Moore-Abstimmung“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser DSA Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede DSA Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Divide-and-Conquer-Vorlage
- Inversionen mit modifiziertem Merge Sort zählen
- Majority Element: Boyer-Moore-Abstimmung
- Median zweier sortierter Arrays