Vectorul de frecvență

În multe probleme trebuie să numărăm de câte ori apare fiecare valoare dintr-un șir de numere.

De exemplu:

• care este cel mai frecvent element?
• există elemente care apar o singură dată?
• câte numere distincte avem?

Pentru toate aceste situații, folosim o tehnică foarte importantă: vectorul de frecvență.

Ce este vectorul de frecvență?

Un vector de frecvență este un vector în care fr[x] reține de câte ori apare valoarea x în șirul dat.

Exemplu: șirul 3 1 2 3 1 3

Cum construim vectorul de frecvență?

Ideea:

1. Declarăm un vector fr inițializat cu 0 (global - se face automat).
2. Citim fiecare număr x.
3. Incrementăm fr[x] cu 1.

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int fr[1001]; // frecventa valorilor de la 0 la 1000
int n;

int main()
{
    fin >> n;

    for (int i = 1; i <= n; i++) {
        int x;
        fin >> x;
        fr[x]++;
    }

    return 0;
}

Pas cu pas pentru șirul 3 1 2 3 1 3

La final: fr[1] = 2, fr[2] = 1, fr[3] = 3.

Problema 1: elementul cu frecvența maximă

Afișăm valoarea care apare de cele mai multe ori.

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int fr[1001];
int n;

int main()
{
    int valMax = 0; // cea mai mare valoare citita
    fin >> n;

    for (int i = 1; i <= n; i++) {
        int x;
        fin >> x;
        fr[x]++;
        if (x > valMax) {
            valMax = x;
        }
    }

    int maxFr = 0;
    int elemMax = 0;

    for (int v = 1; v <= valMax; v++) {
        if (fr[v] > maxFr) {
            maxFr = fr[v];
            elemMax = v;
        }
    }

    fout << elemMax << " apare de " << maxFr << " ori";

    return 0;
}

date.in:

8
3 1 2 3 1 3 2 3

date.out:

3 apare de 4 ori

Problema 2: câte elemente distincte?

Un element este distinct dacă apare cel puțin o dată, adică fr[v] > 0.

int cnt = 0;

for (int v = 1; v <= valMax; v++) {
    if (fr[v] > 0) {
        cnt++;
    }
}

fout << cnt;

Exemplu: șirul 3 1 2 3 1 3 are 3 elemente distincte (1, 2, 3).

Problema 3: elementele care apar o singură dată

for (int v = 1; v <= valMax; v++) {
    if (fr[v] == 1) {
        fout << v << " ";
    }
}

Exemplu: șirul 3 1 2 3 1 3 - elementul care apare o singură dată: 2.

Problema 4: afișarea elementelor în ordine crescătoare

Dacă parcurgem vectorul de frecvență de la 1 la valMax și afișăm fiecare valoare de fr[v] ori, obținem șirul sortat!

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int fr[1001];
int n;

int main()
{
    int valMax = 0;
    fin >> n;

    for (int i = 1; i <= n; i++) {
        int x;
        fin >> x;
        fr[x]++;
        if (x > valMax) valMax = x;
    }

    for (int v = 1; v <= valMax; v++) {
        for (int j = 1; j <= fr[v]; j++) {
            fout << v << " ";
        }
    }

    return 0;
}

date.in:

8
3 1 2 3 1 3 2 3

date.out:

1 1 2 2 3 3 3 3

Problema 5: verificare anagramă

Două cuvinte (sau șiruri de numere) sunt anagrame dacă conțin exact aceleași valori, în aceeași cantitate, dar posibil în altă ordine.

Exemplu: 1 2 3 2 și 3 2 1 2 sunt anagrame.

Ideea: construim vectorii de frecvență pentru ambele șiruri și verificăm dacă sunt identici.

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int fr1[1001], fr2[1001];
int n, m;

int main()
{
    fin >> n;
    for (int i = 1; i <= n; i++) {
        int x;
        fin >> x;
        fr1[x]++;
    }

    fin >> m;
    for (int i = 1; i <= m; i++) {
        int x;
        fin >> x;
        fr2[x]++;
    }

    if (n != m) {
        fout << "NU";
        return 0;
    }

    int anagrama = 1;

    for (int v = 0; v <= 1000; v++) {
        if (fr1[v] != fr2[v]) {
            anagrama = 0;
        }
    }

    if (anagrama == 1) {
        fout << "DA";
    } else {
        fout << "NU";
    }

    return 0;
}

date.in:

4
1 2 3 2
4
3 2 1 2

date.out:

DA

Dimensiunea vectorului de frecvență

Vectorul trebuie să fie suficient de mare cât cea mai mare valoare posibilă.

Când NU putem folosi vectorul de frecvență?

• Când valorile sunt negative (indicii nu pot fi negativi).
• Când valorile sunt foarte mari (de exemplu 10^9 - vectorul ar fi imens).
• Când valorile sunt numere reale (nu putem indexa cu 3.14).

În aceste cazuri, trebuie alte tehnici (sortare + parcurgere, de exemplu).

Greșeli frecvente

1. Vectorul de frecvență prea mic

int fr[100]; // GRESIT daca valorile pot fi pana la 1000
fr[500]++;   // depasire!

Vectorul trebuie declarat în funcție de valoarea maximă posibilă, nu de n.

2. Confuzia: n vs valMax

• n = câte numere citim
• valMax = cea mai mare valoare din șir

Vectorul de frecvență se parcurge de la 0 (sau 1) la valMax, nu la n.

3. Uitarea că vectorul global e inițializat cu 0

Dacă declari fr global, e automat 0. Dacă îl declari în main(), trebuie inițializat manual:

// In main - trebuie initializat
for (int i = 0; i <= 1000; i++) {
    fr[i] = 0;
}

La concursuri, cel mai simplu: declară global.

4. Parcurgerea frecvenței până la n în loc de valMax

// GRESIT:
for (int v = 1; v <= n; v++) {

// CORECT:
for (int v = 1; v <= valMax; v++) {

Dacă n = 5 dar una din valori este 100, trebuie să parcurgem până la 100.

Ce să reții

• Vectorul de frecvență numără de câte ori apare fiecare valoare: fr[x]++.
• Funcționează doar pentru valori naturale nu foarte mari.
• Cu el putem: găsi maximul de frecvență, număra elementele distincte, sorta prin numărare, verifica anagrame.
• Dimensiunea vectorului depinde de valoarea maximă, nu de n.
• Declară vectorul global pentru inițializare automată cu 0.
• Este una dintre cele mai folosite tehnici la concursuri.

Probleme

pbinfoUnice→

pbinfoNumere8→

pbinfoCifreord→

pbinfoNrlipsa2→

pbinfoCufere→