AlgoClar

Elementul majoritar — algoritmul de vot Boyer-Moore

Mediu~15 min8 pași

De ce contează?

La o alegere, doi susținători ai unor candidați diferiți se anulează reciproc și pleacă acasă. Dacă un candidat are mai mulți susținători decât toți ceilalți la un loc, vor rămâne în sală doar oameni de-ai lui — oricât de multe anulări ar avea loc. Așa găsești majoritarul fără să numeri tot.

Ce este elementul majoritar?

Într-un vector cu n elemente, majoritarul e valoarea care apare strict de mai mult de n/2 ori. Dacă există, e unic — două valori cu peste n/2 apariții ar depăși împreună n elemente.

Exemplu: v = {2, 2, 1, 2, 3, 2, 2}, n = 7. Valoarea 2 apare de 5 ori (5 > 3), deci e majoritară.

Soluția simplă cu vector de frecvență

Dacă valorile sunt mici, numeri aparițiile într-un vector frecv și cauți una cu frecv[x] > n/2. Costă O(n) timp și O(valoare_maximă) spațiu. Funcționează, dar consumă memorie când valorile sunt mari.

Algoritmul de vot Boyer-Moore — O(1) memorie

Ideea: ții un candidat și un contor.

  • Contor 0 → candidat nou = elementul curent, contor 1.
  • Element egal cu candidatul → contor +1.
  • Element diferit → contor -1 (o anulare reciprocă).

La final, candidatul rămas e singurul posibil majoritar.

Observația-cheie

Fiecare element diferit „anulează" o apariție a candidatului. Dacă majoritarul apare de peste n/2 ori, are mai multe apariții decât toate celelalte la un loc, deci nu poate fi anulat complet — supraviețuiește ca ultim candidat.

Pas cu pas

Pe v = {2, 2, 1, 2, 3, 2, 2}:

i=0: x=2  contor 0 -> candidat=2, contor=1
i=1: x=2  ==cand   -> contor=2
i=2: x=1  !=cand   -> contor=1
i=3: x=2  ==cand   -> contor=2
i=4: x=3  !=cand   -> contor=1
i=5: x=2  ==cand   -> contor=2
i=6: x=2  ==cand   -> contor=3

Candidat final: 2. Starea contorului ca diagramă, urmărind „energia" candidatului:

1
2
1
2
1
2
3
Valoarea contorului după fiecare pas: scade la întâlnirea altui element, crește la regăsirea candidatului. Nu ajunge niciodată la 0 aici, deci 2 rezistă.

A doua parcurgere: verificarea

Votul dă mereu un candidat, chiar dacă vectorul nu are majoritar. Confirmă numărând:

#include <iostream>
using namespace std;

int main() {
    int v[7] = {2, 2, 1, 2, 3, 2, 2};
    int n = 7;

    // pasul 1: gaseste candidatul
    int candidat = v[0], contor = 0;
    for (int i = 0; i < n; i++) {
        if (contor == 0) candidat = v[i];
        if (v[i] == candidat) contor++;
        else contor--;
    }

    // pasul 2: verifica majoritatea
    int aparitii = 0;
    for (int i = 0; i < n; i++) {
        if (v[i] == candidat) aparitii++;
    }

    if (aparitii > n / 2) cout << candidat << "\n";  // 2
    else cout << "Nu exista element majoritar\n";
    return 0;
}

Complexitate

MetodăTimpSpațiu
vector de frecvențăO(n)O(valoare maximă)
Boyer-MooreO(n)O(1)
Greșeli frecvente

Capcane la elementul majoritar:

  • Omiterea verificării finale: fără a doua parcurgere, returnezi un candidat fals când nu există majoritar.
  • Confuzi „majoritar" cu „cel mai frecvent": cel mai frecvent element poate apărea de mai puțin de n/2 ori; majoritarul cere strict peste n/2.
  • Compari aparitii >= n/2: pentru n par, n/2 apariții nu sunt majoritate. Condiția corectă e > n/2.
  • Resetezi contorul greșit: candidatul se schimbă doar când contorul e exact 0, înainte de a procesa elementul curent.

Recapitulare

  • Majoritarul apare strict de peste n/2 ori; dacă există, e unic.
  • Boyer-Moore găsește candidatul în O(n) timp și O(1) memorie, prin anulări reciproce.
  • E obligatorie o a doua parcurgere care confirmă că aparițiile candidatului depășesc n/2.

Întrebarea 1 / 3

Ce înseamnă „element majoritar” într-un vector cu n elemente?