Vectori de frecvență

De ce contează?

La un sondaj, întrebi 100 de oameni ce culoare preferă. În loc să reții toate răspunsurile, ții un carnețel cu o linie pentru fiecare culoare și pui o liniuță la fiecare răspuns. La final citești direct câți au ales fiecare. Acesta e un vector de frecvență.

Ideea: valoarea devine index

Un vector de frecvență numără aparițiile fiecărei valori. frec[x] = de câte ori apare x. Trucul: folosești valoarea ca index, iar conținutul e numărătoarea.

Algoritm pas cu pas:

Parcurgi datele și incrementezi frec[valoare]:

frec	0	0	3	0	0	2	0	0	1
val	0	1	2	3	4	5	6	7	8

frec[2]=3, frec[5]=2, frec[8]=1: valoarea 2 apare de 3 ori, 5 de 2 ori, 8 o dată. Restul valorilor au frecvența 0.

Implementare C++

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int frec[1001] = {0};           // initializat cu 0
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        frec[x]++;                  // o aparitie in plus pentru valoarea x
    }

    // afisam fiecare valoare si frecventa ei
    for (int val = 0; val <= 1000; val++) {
        if (frec[val] > 0) {
            cout << val << " apare de " << frec[val] << " ori\n";
        }
    }
    return 0;
}

Observația-cheie

Cu vectorul de frecvență răspunzi instant la întrebări de tipul „de câte ori apare x?" (frec[x]) sau „care valoare apare cel mai des?" — o singură parcurgere a lui frec. Fără el ai recalcula de fiecare dată, O(n) per întrebare.

La ce e bun

Cea mai frecventă valoare (modul): parcurgi frec și iei maximul.
Valori duplicate: frec[x] > 1 înseamnă că x apare de mai multe ori.
Sortare prin numărare: rescrii valorile în ordine crescătoare după frec.

Complexitate

Operație	Timp	Spațiu
construire	O(n)	O(V)
întrebare „de câte ori x?"	O(1)	—

unde V = valoarea maximă. Câștigi viteză la întrebări, plătești cu memorie O(V).

Greșeli frecvente

Capcane reale la vectorii de frecvență:

Neinițializat cu 0: frec[x]++ peste gunoi → numărători aberante. Pune = {0}.
Valoare peste dimensiune: aloci frec[1001] dar o valoare e 5000 → scrii în afara vectorului. Dimensionează după valoarea maximă posibilă din enunț.
Valori uriașe: pentru valori până la 10⁹, vectorul nu încape. Folosește map<int,int>.
Valori negative: indicii pornesc de la 0; pentru valori negative adaugă un offset (frec[x + OFFSET]).

Vizualizare

Urmărește cum fiecare element citit ridică bara valorii corespunzătoare în vectorul de frecvență:

Indiciu

Observă că valoarea citită nu se stochează „pe rând", ci ridică direct coloana ei. Două apariții ale aceleiași valori ridică aceeași coloană de două ori.

De reținut

Vector de frecvență: valoarea = index, conținutul = numărul de apariții (frec[x]).
Construire O(n), întrebări O(1); inițializează cu 0.
Memorie O(V) → pentru valori uriașe sau negative fără offset, folosește map.