Vectorul de frecvență: tehnica cea mai utilă la BAC Informatică

Dacă ar fi să alegi o singură tehnică pentru problema de eficiență de la Subiectul III, la BAC informatică, aceea ar fi vectorul de frecvență. Ideea: în loc să memorezi toate numerele citite, numeri de câte ori apare fiecare valoare posibilă. Funcționează când valorile sunt dintr-un interval mic (de exemplu [0, 1000] sau cifre de la 0 la 9) și transformă multe probleme de tip „compară fiecare cu fiecare” într-o singură parcurgere.

Ideea de bază

Declari un vector fr cu câte o poziție pentru fiecare valoare posibilă. fr[x] reține de câte ori a apărut valoarea x. La fiecare număr citit, faci fr[x]++. Atât.

Exemplu: se citesc numerele 3 7 3 0 7 3. După citire, fr[0] = 1, fr[3] = 3, fr[7] = 2, iar restul pozițiilor sunt 0.

Observă că valoarea citită devine indice. De aici și condiția de folosire: valorile trebuie să fie întregi nenegative (sau ușor de transformat în indici) și să aparțină unui interval suficient de mic cât să încapă un vector de dimensiunea lui în memorie.

Program complet: valorile care apar de cele mai multe ori

Fișierul bac.txt conține cel mult 10⁶ numere naturale din intervalul [0, 1000], separate prin spații. Afișați, în ordine crescătoare, valorile care apar de cele mai multe ori în fișier.

#include <fstream>
#include <iostream>
using namespace std;

int fr[1001];   // global, deci inițializat cu 0

int main()
{
    ifstream fin("bac.txt");
    int x;
    while (fin >> x)
        fr[x]++;

    int mx = 0;
    for (int v = 0; v <= 1000; v++)
        if (fr[v] > mx) mx = fr[v];

    for (int v = 0; v <= 1000; v++)
        if (fr[v] == mx)
            cout << v << " ";
    return 0;
}

Pentru fișierul 3 7 3 0 7 3 se afișează 3. Pentru 5 2 5 2 9 se afișează 2 5 — în ordine crescătoare fără nicio sortare, pentru că parcurgem indicii de la mic la mare.

De ce e eficient? Citirea face o singură trecere prin cele n numere, iar parcurgerea vectorului de frecvență are mereu 1001 pași, oricât de multe numere sunt în fișier. Timpul este O(n + 1001), adică liniar. Memoria: un vector de 1001 de întregi, în loc de unul cu 10⁶ elemente în care să păstrezi toate numerele. Dacă ai fi memorat numerele și ai fi numărat aparițiile fiecăruia cu încă o buclă, ar fi ieșit în jur de n² operații — de ordinul 10¹² pentru n = 10⁶, mult prea mult.

Alte întrebări la care răspunde vectorul de frecvență

• Câte valori distincte? Numeri pozițiile cu fr[v] > 0.
• Afișarea tuturor valorilor sortate (sortare prin numărare): pentru fiecare v de la 0 la 1000, afișezi v de fr[v] ori. Pentru 3 7 3 0 7 3 rezultă 0 3 3 3 7 7.
• Valorile care apar o singură dată: fr[v] == 1.
• Cea mai mică valoare din interval care lipsește: prima poziție cu fr[v] == 0.
• Afișare în ordine descrescătoare: parcurgi indicii de la 1000 spre 0.

Frecvența cifrelor unui număr

Un caz foarte des întâlnit e vectorul de frecvență pe cifre, cu doar 10 poziții. Exemplu: două numere sunt „formate din aceleași cifre” (fiecare cifră apare de același număr de ori în ambele) dacă vectorii lor de frecvență pe cifre coincid. 1223 și 3212 au amândouă un 1, doi de 2 și un 3, deci da; 1223 și 1233 nu.

#include <iostream>
using namespace std;

bool aceleasiCifre(int a, int b)
{
    int fa[10] = {0}, fb[10] = {0};    // local, deci inițializat explicit
    do { fa[a % 10]++; a /= 10; } while (a > 0);
    do { fb[b % 10]++; b /= 10; } while (b > 0);
    for (int c = 0; c <= 9; c++)
        if (fa[c] != fb[c]) return false;
    return true;
}

int main()
{
    cout << aceleasiCifre(1223, 3212) << " " << aceleasiCifre(1223, 1233);   // 1 0
    return 0;
}

Cu aceeași idee afli cel mai mare număr care se poate forma din cifrele lui n: parcurgi cifrele de la 9 la 0 și „lipești” fiecare cifră c de fr[c] ori.

Capcane

• Vector neinițializat: un vector de frecvență local trebuie pus pe 0 (= {0} sau o buclă); cel global e deja 0.
• Dimensiune greșită: pentru valori din [0, 1000] ai nevoie de 1001 poziții, nu 1000.
• Valori negative: nu pot fi indici direct. Dacă valorile sunt din [−500, 500], folosești fr[x + 500] și un vector de 1001 de elemente.
• Interval prea mare: pentru valori până la 10⁹, vectorul de frecvență nu mai încape; acolo cauți altă idee (de exemplu, sortare sau o prelucrare „din mers”).