Elementul majoritar: votul Boyer–Moore în C++

Un element este majoritar dacă apare strict de mai mult de n/2 ori. În 2 1 2 2 3, valoarea 2 apare de trei ori din cinci și este majoritară. În 1 1 2 2 3, niciuna nu este majoritară, chiar dacă există valori mai frecvente decât altele.

Anularea perechilor diferite

Dacă eliminăm două valori diferite, una majoritară rămâne majoritară în datele rămase, dacă acestea sunt nevide. Cel mult una dintre cele eliminate poate fi valoarea majoritară. Acest argument stă la baza algoritmului de vot Boyer–Moore; numele de aici desemnează algoritmul pentru majoritate, nu algoritmul de căutare în text cu nume asemănător.

Păstrăm un candidat și o balanță. Când balanța este zero, alegem valoarea curentă drept candidat. O valoare egală îl susține și mărește balanța. O valoare diferită anulează un vot și o micșorează. Balanța nu este frecvența candidatului în întregul vector.

Citim 1≤n≤1000 și n întregi. Afișăm majoritarul sau NU EXISTA. Sortarea nu este necesară. Folosim indici de la 0 și o capacitate clasică de 1000 de elemente.

În 2,1,2,2,3, candidatul final este 2. Verificarea separată găsește trei apariții, strict mai mult decât jumătate din cinci.Mărește schema ↗

Varianta cu tablou clasic

#include <iostream>
using namespace std;
int main() {
    int n; cin >> n;
    int a[1000];
    for(int i=0;i<n;++i) cin >> a[i];
    int candidat=0,balanta=0;
    for(int i=0;i<n;++i) {
        if(balanta==0) candidat=a[i];
        if(a[i]==candidat) ++balanta; else --balanta;
    }
    int aparitii=0;
    for(int i=0;i<n;++i) if(a[i]==candidat) ++aparitii;
    if(aparitii>n/2) cout << candidat << '\n';
    else cout << "NU EXISTA\n";
}

Varianta echivalentă cu std::vector

Păstrăm limitele intrării și aceleași rezultate. Tabloul clasic rezervă capacitatea maximă; vectorul construiește numărul de elemente necesare. Indicii folosiți de algoritm rămân aceiași.

#include <vector>

#include <iostream>
using namespace std;
int main() {
    int n; cin >> n;
    vector<int> a(n);
    for(int i=0;i<n;++i) cin >> a[i];
    int candidat=0,balanta=0;
    for(int i=0;i<n;++i) {
        if(balanta==0) candidat=a[i];
        if(a[i]==candidat) ++balanta; else --balanta;
    }
    int aparitii=0;
    for(int i=0;i<n;++i) if(a[i]==candidat) ++aparitii;
    if(aparitii>n/2) cout << candidat << '\n';
    else cout << "NU EXISTA\n";
}

A doua parcurgere este obligatorie

Pentru 1 2 3, primul 1 și 2 se anulează, iar candidatul final devine 3. El nu este majoritar. Prima parcurgere garantează doar că, dacă există un majoritar, acesta este candidatul rămas. Nu garantează existența lui.

De aceea numărăm aparițiile candidatului și cerem aparitii>n/2. Pentru n par, exact jumătate nu este suficient. Pentru n impar, împărțirea întreagă face comparația corectă: la n=5 sunt necesare cel puțin trei apariții.

Două parcurgeri succesive dau timp O(n), nu O(n²). Starea suplimentară are dimensiune constantă, O(1), iar vectorul ocupă O(n) memorie. Dacă datele pot fi recitite dintr-o sursă, verificarea poate folosi o a doua citire; într-un flux care dispare, candidatul singur nu ajunge.

Exersează

7 are majoritarul 7. 4 4 1 1 nu are majoritar. -2 -2 5 -2 îl are pe -2, deci nu putem folosi zero ca semnal universal de absență. Trasează separat candidatul și balanța pentru 1 2 3, apoi verifică de ce rezultatul primei etape nu este încă răspunsul.

Revezi frecvențele, parcurgerile și costul algoritmilor.

Întrebări frecvente

Ce este un element majoritar?

O valoare care apare strict de mai mult de n/2 ori într-un vector de n elemente. A fi cea mai frecventă valoare nu este suficient dacă pragul de majoritate nu este depășit.

Ce găsește prima parcurgere Boyer-Moore?

Un candidat la majoritate, prin anularea perechilor de valori diferite. Dacă majoritatea nu este garantată de enunț, candidatul trebuie verificat prin numărarea aparițiilor sale într-o a doua parcurgere.

Ce complexitate are verificarea elementului majoritar?

Cele două parcurgeri au împreună timp O(n). Candidatul și contoarele cer O(1) memorie auxiliară, pe lângă stocarea datelor necesare celei de-a doua verificări.