Lista de frecvențe

O listă de frecvențe arată de câte ori apare fiecare valoare dintr-un domeniu cunoscut. Pentru șirul $[4;1;4]$, valoarea 1 apare o dată, iar valoarea 4 de două ori. Metoda folosește un tablou de contoare indexat prin valoare; este practică dacă valorile posibile sunt întregi într-un interval mic.

Când valorile unui șir sunt numere întregi dintr-un interval mic și cunoscut, se poate folosi un tablou de frecvențe: fr[x] păstrează de câte ori apare valoarea x. Pentru valori de la 0 la $M$ se declară $M+1$ contoare inițializate cu 0, iar fiecare valoare citită mărește cu 1 contorul de la poziția ei. Construirea cere $n$ pași pentru cele $n$ valori, deci timp proporțional cu $n+M$, iar memoria este proporțională cu $M$. Suma frecvențelor este $n$, ceea ce oferă o verificare simplă. Pentru valori dintr-un interval $[L;R]$ care nu începe de la 0, indicele se calculează x - L. Valorile trebuie să fie în interval: o valoare prea mare produce IndexError în Python (sau acces în afara tabloului în C++), iar un indice negativ în Python numără de la sfârșitul listei și mărește fără avertisment contorul altei valori.

Exemplul 1 — frecvențele valorilor 1, 2 și 3. Pentru valori între 0 și 3 se pregătesc patru contoare:

v = [2, 1, 2, 3, 2]
frecventa = [0] * 4
for x in v:
    frecventa[x] += 1
print(frecventa[1], frecventa[2], frecventa[3])

După valoarea 2 vectorul contoarelor este [0,0,1,0]; după 1 devine [0,1,1,0]; după al doilea 2, [0,1,2,0]; după 3, [0,1,2,1]; după ultimul 2, [0,1,3,1]. Programul afișează 1 3 1. Suma frecvențelor este 5, egală cu numărul de elemente din v.

Exemplul 2 — valoarea cea mai frecventă. După construirea tabloului se caută maximul frecvențelor. Pentru șirul $3,1,3,2,1,3,2,2$ frecvențele sunt: 1 apare de 2 ori, 2 de 3 ori, 3 de 3 ori. Frecvența maximă este 3, iar valorile 2 și 3 au această frecvență. Dacă enunțul cere cea mai mică valoare cu frecvență maximă, parcurgi contoarele în ordinea valorilor și actualizezi maximul numai când găsești o frecvență strict mai mare: răspunsul este 2.

#include <iostream>
using namespace std;
int main() {
    int v[] = {3, 1, 3, 2, 1, 3, 2, 2}, n = 8;
    int fr[4] = {0};
    for (int i = 0; i < n; ++i)
        ++fr[v[i]];
    int valoare = 0;
    for (int x = 1; x <= 3; ++x)
        if (fr[x] > fr[valoare])
            valoare = x;
    cout << valoare << ' ' << fr[valoare];
    return 0;
}

Programul afișează 2 3. Condiția fr[x] > fr[valoare] este strictă, deci valoarea 3, cu aceeași frecvență ca 2, nu o înlocuiește. Valoarea 0, cu frecvența 0, pornește ca „cea mai bună până acum” și este înlocuită de prima valoare care apare.

Exemplul 3 — interval care nu pornește de la 0. Dacă valorile sunt cuprinse între 10 și 14, se folosesc cinci contoare și indicele este x - 10: valoarea 12 mărește contorul de la poziția 2. Pentru șirul $12,10,12,14$ contoarele finale sunt [1, 0, 2, 0, 1], deci 10 apare o dată, 12 de două ori și 14 o dată. Fără transformarea x - 10, indicii 10–14 ar ieși din tablou. Valorile cu frecvența 1 sunt cele care apar o singură dată, iar cele cu frecvența 0 lipsesc din șir.

Exemplul 4 — valorile distincte. Numărul valorilor distincte este numărul contoarelor nenule. Pentru șirul $5,2,5,7,2,5$, cu valori între 0 și 7, tabloul final are fr[2] = 2, fr[5] = 3, fr[7] = 1, iar celelalte contoare sunt 0. Trei contoare sunt nenule, deci șirul are 3 valori distincte: 2, 5 și 7. Verificarea cu suma frecvențelor este $2+3+1=6$, egală cu numărul de elemente. O valoare apare o singură dată exact când contorul ei este 1: aici, valoarea 7.

Greșeli frecvente

• Greșit: frecvențele se calculează numărând în tablou pozițiile valorilor.
  Corect: fiecare valoare citită mărește contorul de la indicele egal cu valoarea ei.
• Greșit: un tablou de frecvențe merge pentru orice valori întregi.
  Corect: este potrivit când valorile sunt într-un interval mic și cunoscut.
• Greșit: o valoare negativă poate fi folosită direct ca indice.
  Corect: indicele se deplasează cu limita inferioară a intervalului.

Înainte și după