Elementul majoritar

De ce contează?

Într-o sală, oameni cu tricouri de culori diferite. Regula: orice doi oameni cu culori diferite pleacă împreună. Dacă o culoare e în majoritate (peste jumătate), oamenii ei nu pot fi „epuizați" complet — la final rămân doar ei. Așa găsești elementul majoritar.

Ce este elementul majoritar

Un element majoritar apare de strict mai mult de n/2 ori. Dacă există, e unic: nu pot fi două valori care depășesc fiecare jumătatea vectorului.

Soluția simplă (și limita ei)

Cu un vector de frecvență numeri aparițiile și verifici care depășește n/2 — O(n) timp, dar O(V) memorie. Pentru valori uriașe, vectorul de frecvență nu încape. Boyer-Moore rezolvă în O(1) memorie.

Algoritmul de vot Boyer-Moore

Ții un candidat și un contor. Parcurgi vectorul:

contor 0 → candidatul devine valoarea curentă, contor = 1.
valoarea = candidat → contor++.
valoare ≠ candidat → contor−− (o „anulare").

Algoritm pas cu pas:

element	candidat	contor
2	2	1
2	2	2
1	2	1
2	2	2
3	2	1
2	2	2
2	2	3

Candidat final: 2. Apare de 5 ori din 7 → 5 > 3 → e majoritar.

Valoarea 2 (evidențiată) apare de 5 ori din 7 — depășește jumătatea. Anulările cu 1 și 3 nu o pot elimina.

Implementare C++

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int v[1000];
    for (int i = 0; i < n; i++) cin >> v[i];

    // pasul 1: gasim candidatul (votul)
    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: VERIFICAM candidatul
    int aparitii = 0;
    for (int i = 0; i < n; i++) {
        if (v[i] == candidat) aparitii++;
    }
    if (aparitii > n / 2) cout << candidat << "\n";
    else cout << "nu exista element majoritar\n";
    return 0;
}

Observația-cheie

Cei doi pași sunt amândoi necesari. Votul găsește un candidat, dar nu garantează că el chiar depășește n/2. A doua trecere îi numără aparițiile reale — fără ea, ai raporta un candidat fals când nu există majoritar.

De ce funcționează

Fiecare „anulare" elimină o pereche de valori diferite. O valoare care apare de peste n/2 ori are mai multe apariții decât toate celelalte la un loc — nu poate fi anulată complet, deci supraviețuiește ca și candidat final.

Complexitate

Metodă	Timp	Spațiu
Boyer-Moore	O(n)	O(1)
vector de frecvență	O(n)	O(V)

Greșeli frecvente

Capcane reale la elementul majoritar:

Sari verificarea: raportezi candidatul votului fără a doua trecere → răspuns greșit când nu există majoritar.
>= n/2 în loc de > n/2: majoritar înseamnă strict peste jumătate. Cu >= poți accepta o valoare care apare exact n/2 ori.
n/2 cu împărțire întreagă: pentru n impar, n/2 se rotunjește în jos — corect aici fiindcă vrei strict mai mult. Dar fii atent la sensul comparației.
Resetezi candidatul greșit: schimbi candidatul când contorul e 0 înainte de a-l compara cu elementul curent — ordinea instrucțiunilor contează.

De reținut

Majoritar = apare strict > n/2 ori; dacă există, e unic.
Boyer-Moore: candidat + contor, anulezi perechile diferite — O(n) timp, O(1) memorie.
Verifică mereu candidatul printr-o a doua trecere (aparitii > n/2).