Elemento maggioritario: voto di Boyer-Moore
Trovi l'elemento che compare più di n/2 volte usando l'algoritmo di voto di Boyer-Moore, con tempo lineare e spazio O(1), e ne dimostri la correttezza.
Elemento maggioritario: voto di Boyer-Moore è una lezione DSA Interview Prep gratuita su CoddyKit. Questa è la lezione 3 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento DSA Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso DSA Interview Prep include 4 lezioni in totale.
Il problema dell'elemento maggioritario
Elemento maggioritario (LeetCode 169): trovi l'elemento che compare più di n/2 volte in un array di lunghezza n. L'elemento maggioritario esiste sempre, come garantito dal problema. Per [3, 2, 3], la risposta è 3. Per [2, 2, 1, 1, 1, 2, 2], la risposta è 2 (compare 4 volte su 7). Gli approcci vanno dall'ordinamento in O(n log n) all'elegante algoritmo di voto di Boyer-Moore, che opera in O(n) tempo e O(1) spazio.
# 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())})')Approcci precedenti a Boyer-Moore
Tre approcci precedenti a quello ottimale: (1) Ordinamento: si ordina l'array; l'elemento centrale è sempre quello maggioritario (poiché compare >n/2 volte). O(n log n), spazio O(1). (2) Hash map: si contano le frequenze e si restituisce l'elemento con conteggio > n/2. Tempo O(n), spazio O(n). (3) Campionamento casuale: si sceglie un elemento a caso e si verifica che compaia >n/2 volte; il numero atteso di tentativi è O(1) (l'elemento maggioritario viene scelto con probabilità >1/2). Boyer-Moore raggiunge deterministicamente tempo O(n) e spazio O(1).
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)) # 2Algoritmo di voto di Boyer-Moore
L'algoritmo di voto di Boyer-Moore mantiene un candidate e un count. Si percorre l'array: se count == 0, si imposta l'elemento corrente come nuovo candidate. Se l'elemento corrente coincide con candidate, si incrementa count. Altrimenti, si decrementa count. Alla fine, candidate è l'elemento maggioritario. Il metodo funziona perché l'elemento maggioritario compare più volte di tutti gli altri elementi messi insieme: non può mai essere completamente eliminato dai voti contrari.
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])) # 1Intuizione alla base dell'algoritmo
Intuizione: immagini che ogni elemento «annulli» un'occorrenza di un elemento diverso. L'elemento maggioritario (count > n/2) ha più occorrenze di tutti gli altri elementi messi insieme, quindi può annullare tutti gli elementi non maggioritari e avere ancora delle occorrenze rimanenti. La variabile count tiene traccia del vantaggio netto del candidate corrente. Quando count raggiunge 0, il candidate corrente è stato annullato da altrettanti elementi avversari: quello che emerge successivamente diventa il nuovo candidate.
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=1Dimostrazione della correttezza
Dimostrazione: sia m l'elemento maggioritario con conteggio k > n/2. Al termine dell'algoritmo, può essere un elemento non maggioritario a essere il candidate? Perché ciò accada, m deve essere stato completamente annullato. Ogni annullamento di m richiede un'occorrenza di un altro elemento. Per annullare tutte le k occorrenze di m, servono almeno k occorrenze di elementi diversi da m. Ma k > n/2 e il totale degli elementi diversi da m è n-k < n/2 < k. Contraddizione: m non può essere completamente annullato.
# 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]])Elemento maggioritario II: più di n/3
Elemento maggioritario II (LeetCode 229): trovi tutti gli elementi che compaiono più di n/3 volte. Al massimo 2 elementi possono soddisfare questa condizione (poiché 3 × n/3 = n). Si estende Boyer-Moore mantenendo due candidati con due conteggi. Quando un nuovo elemento non coincide con nessuno dei due candidati e entrambi i conteggi sono positivi, si decrementano entrambi. Un passaggio finale di verifica conferma quali candidati superano effettivamente n/3.
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]Boyer-Moore generalizzato: maggioranza n/k
Boyer-Moore si generalizza per trovare tutti gli elementi che compaiono più di n/k volte usando k-1 candidati. Al massimo k-1 elementi possono soddisfare questa condizione. Si mantengono k-1 coppie (candidate, count). Quando nessuna coincide e tutti i conteggi sono positivi, si decrementano tutti i conteggi di 1. Questo algoritmo generalizzato opera in tempo O(n) e spazio O(k). Nei colloqui, di solito è sufficiente conoscere l'estensione con due candidati (n/3).
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)Elemento maggioritario con divide et impera
Un approccio divide et impera: si divide l'array a metà. L'elemento maggioritario dell'intero array deve essere maggioritario in almeno una delle due metà (se non fosse maggioritario in nessuna delle due, non potrebbe comparire più di n/2 volte complessivamente). Si trova ricorsivamente l'elemento maggioritario di ciascuna metà. Se le due metà concordano, quella è la risposta. Altrimenti, si contano entrambi i candidati nell'intero array e si restituisce quello con più occorrenze. Ricorrenza: 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 e gli altri metodi
Confronto tra i metodi per l'elemento maggioritario: Ordinamento: tempo O(n log n), spazio O(1), distruttivo. Hash map: tempo O(n), spazio O(n), non distruttivo. Divide et impera: tempo O(n log n), spazio O(log n) per lo stack delle chiamate. Boyer-Moore: tempo O(n), spazio O(1), una sola scansione, non distruttivo. Boyer-Moore è strettamente superiore per questo problema. Nei colloqui, inizi sempre da Boyer-Moore dopo aver menzionato brevemente l'approccio più semplice con hash map.
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}')Quando la maggioranza non è garantita
Boyer-Moore restituisce sempre un candidate, ma questo potrebbe non essere un elemento maggioritario se non ne esiste alcuno. Se il problema non garantisce l'esistenza di un elemento maggioritario, è necessario verificarlo: dopo Boyer-Moore, si contano le occorrenze del candidate. Se count > n/2, è l'elemento maggioritario. Altrimenti, si restituisce -1 oppure None. Questa verifica aggiunge un altro passaggio O(n), ma mantiene l'algoritmo complessivamente in tempo O(n) e spazio O(1).
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)Svolgimento del colloquio
Approccio da seguire in un colloquio per l'elemento maggioritario: (1) si menzionano l'ordinamento (O(n log n), O(1)) e la hash map (O(n), O(n)) come approcci iniziali. (2) Si introduce Boyer-Moore come soluzione ottimale O(n) O(1). (3) Si spiega l'intuizione dell'annullamento: l'elemento maggioritario non può essere annullato perché compare più volte di tutti gli altri elementi messi insieme. (4) Si scrive il codice in modo chiaro in 5 righe. (5) Si gestisce il caso limite: se la maggioranza non è garantita, si aggiunge un passaggio di verifica. Questa struttura dimostra un approccio sistematico anche sotto pressione.
# 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)')Verifica rapida
Metta alla prova la Sua comprensione dei concetti di Strutture dati e algoritmi — Preparazione ai colloqui di programmazione trattati in questa lezione.
Riepilogo della lezione
In questa lezione ha imparato che: il voto di Boyer-Moore trova l'elemento maggioritario in tempo O(n) e spazio O(1), usando un candidate e un count che annullano gli elementi non maggioritari, l'algoritmo si estende alla maggioranza n/3 con due candidati e richiede un passaggio di verifica quando la maggioranza non è garantita e la dimostrazione si basa sul fatto che l'elemento maggioritario ha più occorrenze di tutti gli altri elementi messi insieme, rendendo impossibile il suo completo annullamento. Successivamente si affronterà il problema della mediana di due array ordinati usando la ricerca binaria sul confine della partizione.
Domande Frequenti
La lezione «Elemento maggioritario: voto di Boyer-Moore» è gratuita?
Sì — il testo completo di «Elemento maggioritario: voto di Boyer-Moore» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso DSA Interview Prep, passa a CoddyKit PRO. Il corso DSA Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Elemento maggioritario: voto di Boyer-Moore»?
Trovi l'elemento che compare più di n/2 volte usando l'algoritmo di voto di Boyer-Moore, con tempo lineare e spazio O(1), e ne dimostri la correttezza. Eserciti DSA Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare DSA Interview Prep?
Non è richiesta alcuna esperienza precedente. DSA Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 3 di 4.
Quanto tempo richiede la lezione «Elemento maggioritario: voto di Boyer-Moore»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione DSA Interview Prep?
Sì. Ogni lezione DSA Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Schema divide et impera
- Conteggio delle inversioni con merge sort modificato
- Elemento maggioritario: voto di Boyer-Moore
- Mediana di due array ordinati