Programare Competitivă

Algoritmul Boyer-Moore pentru elementul majoritar

Elementul majoritar al unui vector este elementul care apare mai mult de jumătate din timp (> n/2 apariții).

Un vector are cel mult un singur element majoritar (dacă există).

Problema

Vector cu n elemente. Să se găsească elementul majoritar, dacă există.

Exemple:
[3, 2, 3, 3, 5, 3, 3]  → 3 (apare de 5 ori, n=7, 5 > 3.5)
[1, 2, 3, 4]           → nu există element majoritar
[5, 5, 5, 1, 2]        → 5 (apare de 3 ori, n=5, 3 > 2.5)

Soluții clasice

Soluția 1: vector de frecvență

int fr[1000001];
for (int i = 0; i < n; i++)
    fr[v[i]]++;

for (int i = 0; i < n; i++)
    if (fr[v[i]] > n / 2) {
        cout << v[i];
        break;
    }

Complexitate: O(n) timp, O(valMax) memorie. Dar necesită vector de frecvență mare dacă valorile sunt mari.

Soluția 2: sortare

sort(v, v + n);
cout << v[n / 2]; // elementul majoritar e la mijloc (dacă există)

Complexitate: O(n log n) timp, O(1) memorie extra. Dar trebuie să verificăm la final că e chiar majoritar.

Soluția 3: Boyer-Moore

O(n) timp, O(1) memorie - cea mai eficientă.

Algoritmul Boyer-Moore

Ideea

Menținem un candidat și un contor. Parcurgem vectorul:

  1. Dacă contor = 0: setăm elementul curent ca nou candidat, contor = 1.
  2. Dacă elementul curent = candidat: contor++.
  3. Dacă elementul curent ≠ candidat: contor–.

La final, candidatul este potențialul element majoritar. Verificăm cu o a doua parcurgere dacă chiar e majoritar.

De ce funcționează?

Gândește-te la elemente ca la voturi. Candidatul e cel care conduce. Când vine un vot contra (element diferit), contorul scade - ca și cum candidatul ar “pierde” un vot în favoarea altuia. Dacă contorul ajunge la 0, candidatul se schimbă.

Dacă un element apare mai mult de jumătate din timp, va rezista tuturor “anulărilor” și va rămâne candidat la final.

Cod

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int v[100001];
int n;

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

    int candidat = 0;
    int contor = 0;

    // Pasul 1: găsim candidatul
    for (int i = 0; i < n; i++) {
        if (contor == 0) {
            candidat = v[i];
            contor = 1;
        } else if (v[i] == candidat) {
            contor++;
        } else {
            contor--;
        }
    }

    // Pasul 2: verificăm dacă e chiar majoritar
    int nrAparitii = 0;
    for (int i = 0; i < n; i++)
        if (v[i] == candidat)
            nrAparitii++;

    if (nrAparitii > n / 2)
        fout << candidat;
    else
        fout << "Nu exista element majoritar";

    return 0;
}

date.in:

7
3 2 3 3 5 3 3

date.out:

3

Pas cu pas

Vector: 3 2 3 3 5 3 3, n = 7

i v[i] candidat contor Acțiune
0 3 3 1 contor=0 → setăm candidat=3
1 2 3 0 2 ≠ 3 → contor–
2 3 3 1 contor=0 → setăm candidat=3 (din nou)
3 3 3 2 3 = 3 → contor++
4 5 3 1 5 ≠ 3 → contor–
5 3 3 2 3 = 3 → contor++
6 3 3 3 3 = 3 → contor++

Candidat final: 3. Verificăm: 3 apare de 5 ori, 5 > 7/2 = 3.5 → DA, este majoritar.

De ce e nevoie de verificare la pasul 2?

Dacă nu există element majoritar, algoritmul tot returnează un candidat (ultimul care a câștigat “cursa”), dar nu e garantat că apare de mai mult de n/2 ori.

Exemplu: [1, 2, 3, 4] - niciun element nu e majoritar, dar algoritmul returnează un candidat (probabil 4). A doua parcurgere ne confirmă că nu e majoritar.

Exemplu în care NU există majoritar

Vector: 1 2 3 4 5, n = 5

i v[i] candidat contor
0 1 1 1
1 2 1 0
2 3 3 1
3 4 3 0
4 5 5 1

Candidat final: 5. Verificare: 5 apare o singură dată, 1 > 5/2 = 2.5? NU. Deci nu există majoritar.

Complexitate

Timp Memorie
Vector de frecvență O(n) O(valMax)
Sortare O(n log n) O(1) sau O(log n)
Boyer-Moore O(n) O(1)

Boyer-Moore e optim pe ambele dimensiuni.

Extensie: elementele care apar > n/3 ori

Într-un vector pot exista cel mult 2 astfel de elemente. Algoritmul se generalizează cu 2 candidați și 2 contoare.

int c1 = 0, c2 = 0, cnt1 = 0, cnt2 = 0;

for (int i = 0; i < n; i++) {
    if (v[i] == c1) cnt1++;
    else if (v[i] == c2) cnt2++;
    else if (cnt1 == 0) { c1 = v[i]; cnt1 = 1; }
    else if (cnt2 == 0) { c2 = v[i]; cnt2 = 1; }
    else { cnt1--; cnt2--; }
}

// Verificăm c1 și c2 cu o a doua parcurgere

În general, pentru elementele care apar > n/k ori, folosim k-1 candidați.

Demonstrație intuitivă

Imaginează-ți că fiecare element este un jucător într-un turneu. Când apar doi jucători diferiți, ei se “elimină” reciproc (contorul scade).

Un jucător care apare de mai mult de jumătate din timp nu poate fi eliminat de toți ceilalți - vor rămâne din el. Deci la final, el e candidat.

Matematic: dacă elementul X apare de k > n/2 ori, atunci ceilalți sunt n-k < n/2. Fiecare anulare costă câte un X și un non-X. Chiar dacă toți non-X anulează X, rămâne cel puțin k - (n-k) = 2k - n > 0 copii ale lui X.

Greșeli frecvente

1. Uitarea verificării la pasul 2

// GRESIT - nu verificăm că e chiar majoritar
fout << candidat;

Algoritmul returnează un candidat chiar dacă nu există majoritar. Verificarea e obligatorie.

2. > n/2 vs >= n/2

Element majoritar = apare strict mai mult decât jumătate: nrAparitii > n / 2.

Dacă apare exact n/2 ori, NU e majoritar (de exemplu, în [1, 1, 2, 2] niciun element nu e majoritar).

3. Candidatul la primul element

Unele implementări inițializează candidat = v[0] și contor = 1, apoi parcurg de la i = 1. Funcționează la fel, doar o altă formulare.

Ce să reții

  • Element majoritar = apare > n/2 ori. Un vector are cel mult unul.
  • Boyer-Moore găsește candidatul în O(n) cu O(1) memorie.
  • Ideea: elementele diferite se “anulează” reciproc. Cel majoritar îl vom găsi la sfârșit.
  • La final, verificăm cu o a doua parcurgere dacă e chiar majoritar.
  • Extensie: pentru > n/3 avem 2 candidați, pentru > n/k avem k-1.
Cuprins Inapoi Inainte