De ce contează?
Imaginează-ți un registru cu o căsuță pentru fiecare valoare posibilă: una pentru 1, una pentru 2, una pentru 3 și așa mai departe. Iei pe rând fiecare număr din șir și pui un beț în căsuța lui. Când termini, nu mai trebuie să recitești șirul: te uiți direct în căsuța lui 3 și știi instant de câte ori a apărut. Asta e un vector de frecvență.
Intuiția
În loc să întrebi de fiecare dată „de câte ori apare valoarea X?” și să
reparcurgi tot șirul, faci o singură trecere și ții socoteala pe măsură ce
citești. Cheia e că folosești valoarea ca indice: căsuța freq[v] numără
de câte ori a apărut valoarea v. După o parcurgere, orice întrebare despre
apariții se rezolvă cu o singură citire.
Trucul întreg stă într-un singur gest: pentru fiecare element din șir scrii
freq[v[i]]++. Nu cauți valoarea în vector — o folosești ca adresă și
incrementezi direct căsuța ei. Aici numărarea se mută din „caut de fiecare dată”
în „indexez o singură dată”.