De ce contează?
La un recensământ nu întrebi de fiecare casă „câți locuitori sunt în tot orașul?". Treci o dată prin toate casele și bifezi pe o listă. Vectorul de frecvențe face exact asta pentru caractere: o singură trecere prin șir și știi de câte ori apare fiecare literă.
Ce este un vector de frecvențe
Un vector de frecvențe are câte o poziție pentru fiecare caracter posibil și
reține de câte ori apare. Pentru literele mici 'a'..'z' ai nevoie de doar 26 de
poziții, dacă aduci litera la index cu c - 'a'.
Ideea-cheie: în loc să întrebi de n ori „de câte ori apare litera x?" (fiecare
întrebare costând O(n)), numeri totul o singură dată și apoi citești răspunsul
instant din vector.
Algoritmul pas cu pas
Pentru "abracadabra" parcurgem și creștem poziția corespunzătoare:
a -> frecv[0]++ (acum 1)
b -> frecv[1]++ (acum 1)
r -> frecv[17]++ (acum 1)
a -> frecv[0]++ (acum 2)
c -> frecv[2]++
a -> frecv[0]++ (acum 3)
d -> frecv[3]++
a -> frecv[0]++ (acum 4)
b -> frecv[1]++ (acum 2)
r -> frecv[17]++ (acum 2)
a -> frecv[0]++ (acum 5)Frecvențele finale pentru literele care apar:
| frecv | 5 | 2 | 1 | 1 | 2 |
| litera | a | b | c | d | r |
Implementare C++
#include <iostream>
#include <string>
using namespace std;
int main() {
string s = "abracadabra";
int frecv[26] = {0}; // init cu 0, esential
for (char c : s) {
frecv[c - 'a']++; // aduce litera la index 0..25
}
// litera cea mai frecventa
int maxPoz = 0;
for (int i = 1; i < 26; i++) {
if (frecv[i] > frecv[maxPoz]) {
maxPoz = i;
}
}
cout << (char)('a' + maxPoz) << " " << frecv[maxPoz] << endl; // a 5
return 0;
}Complexitate
| Operație | Timp | Spațiu |
|---|---|---|
| Construirea vectorului | O(n) | O(alfabet) |
| Răspuns la o întrebare (apariții, maxim) | O(1) / O(alfabet) | O(1) |
n = lungimea șirului; alfabetul e constant (26 sau 128), deci spațiul e O(1) practic.
Greșeli reale cu vectorii de frecvențe:
- Uiți să inițializezi cu 0.
int frecv[26];fără= {0}conține gunoi → numărători aberante. - Index greșit la litere mari sau cifre.
c - 'a'e corect doar pentru litere mici; pentru text mixt foloseștefrecv[(unsigned char)c]pe 128/256 de poziții. - Acces în afara vectorului. Dacă apare un caracter neașteptat (spațiu, virgulă) și
faci
c - 'a', poți obține index negativ → comportament nedefinit. Filtrează întâi cuisalpha. - Numeri de mai multe ori. Nu reface bucla pentru fiecare literă — vectorul există tocmai ca să răspunzi o singură dată.
Vizualizare
Urmărește cum, la fiecare caracter parcurs, exact o coloană de frecvență crește cu 1:
Recapitulare
- Un vector de frecvențe numără toate caracterele într-o singură trecere O(n).
c - 'a'aduce literele mici la indicii 0..25 (folosește 128 de poziții pentru text mixt).- Inițializează mereu cu 0 și filtrează caracterele din afara alfabetului așteptat.