De ce contează?
Ai două unelte: un caiet cu liste (vectorul simplu) și o tabelă de bifare (vectorul de frecvență). Știi cum funcționează fiecare. Acum trebuie să știi când să deschizi caietul și când să folosești tabela — alegerea greșită costă timp sau memorie.
Regula de decizie
Gândește-te la ce informație ai nevoie din date:
| Întrebare | Instrument |
|---|---|
| „Care e al k-lea element?" | Vector simplu |
| „Câte valori de X sunt?" | Vector de frecvență |
| „Apare X în colecție?" | Vector caracteristic |
| „Care e al doilea maxim?" | Vector simplu (sau sortare) |
| „Câte valori distincte?" | Frecvență — numeri câte frec[i] > 0 |
| Ordinea de apariție contează | Vector simplu |
| Operații rapide cu mulțimi | Vector caracteristic |
Limitele vectorului de frecvență
Vectorul de frecvență e rapid, dar cu cerințe stricte:
- Valorile trebuie să fie întregi (nu reale, nu string-uri).
- Intervalul valorilor trebuie să fie mic și cunoscut (de regulă sub 10⁵–10⁶).
- Dacă valorile merg până la 10⁹,
frec[10^9]nu încape în memorie.
Regula practică: valori în 0..100.000 → vectorul de frecvență e ok. Valori în 0..10⁹ → ai nevoie de altceva (std::map, sortare cu coordonate comprimate etc.).
Ordinea originală se pierde
Frecvența numără, nu memorizează ordinea. Pornind de la 3 1 4 1 5:
Vector original: {3, 1, 4, 1, 5} → ordinea păstrată
frec[1]=2, frec[3]=1, frec[4]=1, frec[5]=1 → ordinea pierdutăDacă la ieșire ai nevoie de „al i-lea element citit", frecvența nu ajunge.
Greșeala 1: Construiești frecvența și vrei după aceea „al câtelea element citit a fost egal cu X" — imposibil. Dacă ai nevoie de indici sau ordine, păstrează și vectorul original.
Greșeala 2: int frec[n] unde n e numărul de elemente — confunzi numărul de elemente cu intervalul valorilor. Dimensiunea lui frec[] e dată de valoarea maximă posibilă + 1, nu de n.
Ghid rapid de alegere
Ai valori întregi în interval mic (< 10⁶)?
DA → consideră vectorul de frecvență / caracteristic
NU → folosește vectorul simplu + altă tehnică
Ai nevoie de ordinea elementelor?
DA → vectorul simplu (păstrezi datele originale)
NU → frecvența poate fi suficientă
Ai nevoie de câte apariții exact?
DA → frecvență
NU (doar prezent/absent) → caracteristic (mai simplu)Recapitulare
- Vector simplu: păstrează valorile în ordine, accesare prin index.
- Vector de frecvență: numără aparițiile în O(1) per interogare, pierde ordinea originală.
- Alegerea depinde de ce întrebare trebuie să răspunzi și de intervalul valorilor.