Elementul majoritar
Suiram are o noua cerinta pentru voi. El va da un vector cu n elemente si va roaga sa gasiti elementul sau majoritar. Un element este considerat majoritar daca apare de cel putin n/2+1 ori in vector.
Sursa: elmaj – infoarena.ro
Problema este destul de simpla, ti se da un vector cu pana la un milion de elemente iar tu trebuie sa determini care numar apare de cele mai multe ori in vector. De asemenea, numerele din vectori sunt numere de la 1 la 2 * (1 miliard).
Exemplu
Daca avem fisierul de intrare
7 3 4 4 3 3 2 3
Atunci in urma executarii algoritmului, rezultatul va fi “3 4” (3 este elementul majoritar si apare de exact 4 ori).
Vector de aparitii ?
Prima idee care iti trece prin cap, atunci cand esti la inceput, in cazul unei astfel de probleme este sa folosesti un vector de aparitiii. Daca te apuci insa si iti calculezi memoria ce urmeaza sa o folosesti, o sa ajungi la concluzia ca o astfel de metoda de abordare a problemei nu este eficienta, pentru ca folosesti foarte multa memorie, ineficient.
Solutia eficienta
Ce stim noi despre elementul majoritar? Acesta trebuie sa apara de CEL PUTIN n / 2 – 1 ori in vectorul nostru. Vom lua vectorul din exemplu pentru a lucra cu el.
La inceput nu putem stii cine apare de cele mai multe ori in vector, asa ca vom “caut un candidat” pentru functia de “element majoritar”. In cazul nostru, primul candidat va fi “3”.
In continuare, trebuie sa avem grija de candidatul nostru, sa tinem cont de cate ori a aparut acesta inainte, si sa ne gandim daca ar fi cazul sa il schimbam, si sa cautam alt candidat. Cum facem asta? Foarte usor!
Luam o variabila de tip int pe care o numim “contor”. De ce contor? Pentru ca acesta va tine cont de aparitiile candidatului nostru pana in prezent. Acesta contor va creste atunci cand intalneste intalneste acelasi numar ca si candidatul si va scade atunci cand numarul intalnit este diferit de candidatul din prezent.
Haide sa urmarim pas cu pas ce se intampla.
Fiecare linie reprezinta valorile variabilelor dupa ce elementul curent a fost analizat
Poate vreodata aceasta metoda sa dea gres? Nu
De ce? Pentru ca mereu elementul majoritar (daca exista) va aparea de n / 2 + 1 ori. Chiar si daca am avea numerele in forma “3 4 3 4 3 4 3” t0t 3 ar fi elementul majoritar. Incearcati sa completati singuri tabelul pentru vectorul.
7 3 4 3 4 3 4 3
Daca la finalul algoritmului nostru, elementul care este “candidat” nu este majoritar, atunci asta inseamna ca acel element nu apare de n / 2 + 1 ori.
Pentru a rezolva complet problema, la finalul algoritmului vom parcurge vectorul si vom numara de cate ori gasim elementul majoritar.
Codul sursa, aici: elmaj.cpp
