Vectori de frecventa

Definiție

Un vector de frecvență este o structură de date utilizată pentru a contoriza de câte ori apare fiecare element (caracter, cifră, număr, etc.) într-o mulțime sau într-un șir.

Este frecvent utilizat în algoritmică pentru a rezolva probleme de tipul: "De câte ori apare un element?"

Reprezentare

Vectorul de frecvență este un tablou (array) în care fiecare poziție reprezintă un element, iar valoarea de la acea poziție reprezintă numărul de apariții al elementului.

Exemplu:

// Vector de frecvență pentru cifre (0-9)
int frecventa[10] = {0}; // Inițializare cu 0

int cifre[] = {3, 5, 3, 9, 5, 5};
int n = sizeof(cifre)/sizeof(cifre[0]);

for (int i = 0; i < n; i++) {
    frecventa[cifre[i]]++;
}
    

Aplicabilitate

• Numărarea frecvenței aparițiilor unui caracter într-un text
• Verificarea dacă două cuvinte sunt anagrame
• Rezolvarea problemelor de tip "majoritatea elementelor"
• Compararea secvențelor de date

Exemplu

Verificarea dacă două cuvinte sunt anagrame folosind vectori de frecvență:

bool suntAnagrame(string a, string b) {
    if (a.size() != b.size()) return false;

    int frecA[26] = {0}, frecB[26] = {0};

    for (char c : a) frecA[c - 'a']++;
    for (char c : b) frecB[c - 'a']++;

    for (int i = 0; i < 26; i++)
        if (frecA[i] != frecB[i])
            return false;

    return true;
}