Alta idee vine de la faptul ca in sirul sortat, elementele de valori egale vor fi pe pozitii consecutive. Astfel numele presedintelui va aparea pe cel putin n/3 + 1 pozitii consecutive. Deci numele presedintelui va aparea sigur pe cel putin una din pozitiile n/3 sau 2n/3 din sir. Astfel putem folosi un algoritm de selectie pentru a gasi in O(n) elementele de pe pozitiile n/3 si 2n/3 si apoi in O(n) putem verifica care dintre acesti doi candidati au castigat.

Daca presupunem ca n e pana in un milion am putea la fiecare pas sa incrementam pentru candidatul votat x numerele a[x / 1000] si a[x % 1000]. Acum pentru a determina candidatul castigator, gasim valoarea p pentru care a[x] > n/3 + 1 si valoarea q pentru care a[y] > n/3 + 1, iar castigatorul va fi p * 1000 + q.
 

O solutie ar fi sa folosim un hash map ce mapeaza numele alegatorilor la numarul de voturi castigate. Solutia aceasta este eficienta dar foloseste O(n) memorie suplimentara pentru structura de date.
Alta solutie este sa facem grupuri de cate trei alegatori cu opinii diferite asupra castigatorului, care se cearta intre ei pana pica jos. Dupa ce am facut toate grupurile de cate trei, ne mai  pot ramane maxim doua optiuni de candidati, in caz contrar mai gaseam un grup de trei votanti cu optiuni diferite. E clar ca dupa ce am eliminat grupurile de cate trei, va exista unul dintre alegatori cu optiunea pentru viitorul presedinte intre alegatorii negrupati, pentru ca acesta e votat de mai mult de n/3 ori. Asa ca pentru a gasi presedintele este de ajuns sa verificam cele doua optiuni ai alegatorilor ramasi negrupati. Aceasta solutie se implementeaza foarte usor si foloseste spatiu suplimentar de memorie constant.

_Articolul a fost inspirat din articolul "Problema majoritatii votului" ce l-am publicat in Ginfo, iar partea cu cearta intre alegatori din R. S. Boyer, J. S. Moore A Fast Majority Vote Algorithm_

_Problema vi se poate parea artificiala, dar desi nu stiu daca se foloseste sau nu la Google, ar putea fi reformulata in aceea de a gasi in mod eficient queriuri foarte frecvente pentru un motor de cautare.  Articolul a fost inspirat din articolul "Problema majoritatii votului" ce l-am publicat in Ginfo, iar partea cu cearta intre alegatori din R. S. Boyer, J. S. Moore A Fast Majority Vote Algorithm_

==BlogCommentCount(topic_id="2350")==