Majority element (Boyer-Moore voting)
Në shqip: Elementi shumicë
ShpjegimiSQ
Gjen elementin që shfaqet më shumë se n/2 herë me O(1) memorie: mban një „kandidat“ dhe një numërues; të njëjtët e rrisin, të ndryshmit e zbresin. Në fund mbetet shumica.
EnglishEN
Finds the element appearing more than n/2 times with O(1) memory: keep a “candidate” and a counter; matches increase it, mismatches decrease it. The majority survives at the end.
Si ta mendosh
Si një betejë ku çdo ushtar i një ane „anulon“ një të anës tjetër — fiton ushtria më e madhe.
Lexoje në anglisht
Like a battle where each soldier cancels one from the other side — the biggest army wins.
Shembull kodipython
kandidati, n = None, 0
for x in v:
if n == 0: kandidati = x
n += 1 if x == kandidati else -1
print(kandidati)