Sari la conținut

Vectori de frecvență

Autor: Ștefan-Cosmin Dăscălescu

Cunoștințe necesare

Introducere#

În multe probleme, suntem nevoiți să lucrăm cu foarte multe valori cuprinse într-un interval relativ mic. Pentru a face lucrul cu ele mai ușor, se impune numărarea lor și păstrarea datelor într-o structură de date potrivită.

Astfel, se impune folosirea unui vector de frecvență.

Definiție

Așa cum sugerează și numele, un vector de frecvență este o structură de date de tip tablou pe care o folosim pentru a ține în memorie de câte ori apare fiecare element într-un șir de numere.

Exemplu

De exemplu, dacă șirul nostru conține valorile \(8, 1, 4, 1, 6, 3, 5, 2, 2, 4\), vectorul de frecvență va avea următoarea formă: \(0, 2, 2, 1, 1, 1, 1, 0, 1\), cu semnificația că \(0\) nu apare deloc, \(1\) apare de două ori, \(2\) apare de două ori, iar celelalte valori, cu excepția lui \(7\), apar o singură dată.

Această structură de date se folosește atunci când numerele (sau în general, datele cu care lucrăm) pot lua puține valori distincte sau se află într-un interval mic.

Observație

În general, vrem să folosim vectorii de frecvență dacă stocarea informațiilor legat de valorile pe care le folosim devine mult mai facilă din punct de vedere al memoriei sau timpului comparat cu stocarea lor în vectorul deja existent. În probleme, acest lucru se remarcă mai ales dacă valorile nu sunt foarte mari (până în \(10^6\)) sau dacă diferența dintre cel mai mare și cel mai mic element este mică.

Pe parcursul acestui articol, voi prezenta câteva probleme, pentru a explica diferitele variații ale acestei metode precum și alte moduri în care putem păstra acest vector în memorie.

Vector caracteristic

În unele cărți și articole, dacă vectorul de frecvență este folosit doar pentru a verifica existența unor valori, se mai folosește denumirea de vector caracteristic.

Problema cifreord de pe pbinfo#

O soluție posibilă pentru această problemă este să sortăm valorile folosind unul din algoritmii de sortare explicat aici.

Totuși, numărul de valori este prea mare și această abordare ar depăși limita de timp alocată. În schimb, ne putem folosi de faptul că lucrăm doar cu cifre zecimale și le putem afișa pe acestea corespunzător cu frecvența lor. Trebuie să avem grijă și să afișăm o linie nouă de fiecare dată când afișăm \(20\) de numere, conform cerinței din enunț.

#include <fstream>
using namespace std;

ifstream fin("cifreord.in");
ofstream fout("cifreord.out");

int main() {
    int n;
    fin >> n;

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

        fr[x]++;
    }

    int cnt = 0; 
    for (int i = 0; i <= 9; i++) {
        while (fr[i] > 0) {
            fout << i << " ";
            cnt++;
            if (cnt == 20) {
                fout << '\n';
                cnt = 0;
            }
            fr[i]--;
        }
    }

    return 0;
}

Problema numere1 de pe pbinfo#

Pentru a rezolva această problemă, cea mai importantă informație pe care o primim din enunț este aceea că valorile care ne interesează sunt strict cele care au trei cifre (cu alte cuvinte, cele între \(100\) și \(999\)). Astfel, se impune crearea unui vector de frecvență care să poată memora aceste valori și după ce citim valorile din șir, se pot afla cu ușurință cele mai mari două valori de trei cifre care nu se află în șir. 

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    int fr[1000] = {0}; // toate valorile sunt initializate cu 0
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;

        if (x >= 100 && x <= 999) {
            fr[x]++;
        }
    }

    int a = 0, b = 0;
    for (int i = 999; i >= 100; i--) {
        if (fr[i] == 0) {
            if (a == 0) {
                a = i;
            }
            else {
                if (b == 0) {
                    b = i;
                }
            }
        }
    }

    if (a == 0 || b == 0) {
        cout << "NU EXISTA";
    }
    else {
        cout << b << " " << a << '\n';
    }
    return 0;
}

Problema nrlipsa2 de pe pbinfo#

Pentru a citi acel număr necunoscut de valori, va trebui să ne bazăm pe o structură repetitivă de tip while. Apoi, pentru a lucra cu valorile din intervalul \([-100, 100]\), trebuie să adaptăm lucrurile la realitatea limbajului C++, și anume la faptul că nu putem păstra indici negativi în vector.

Astfel, în loc să lucrăm cu acel interval, vom vrea să adunăm o valoare (un offset) care să ne asigure că lucrăm cu valori non-negative (astfel, intervalul devine \([0, 200]\)). Ulterior, atunci când afișăm valoarea care nu apare, vom scădea \(100\) din răspuns pentru a întoarce rezultatul la cel real. 

#include <fstream>
using namespace std;

ifstream fin("nrlipsa2.in");
ofstream fout("nrlipsa2.out");

int main() {
    int v[201] = {0};
    int x;

    while (fin >> x) {
        if (x >= -100 && x <= 100) {
            v[x+100]++;
        }
    }

    int gasit = 0;
    for (int i = 0; i <= 200; i++) {
        if (v[i] == 0) {
            fout << i - 100 << '\n';
            // alternativ, puteam da return 0 aici sa iesim din program
            gasit = 1; 
            break;
        }
    }

    if (gasit == 0) {
        fout << "nu exista";
    }

    return 0;
}

Problema mincifre de pe pbinfo#

Pentru a rezolva această problemă, putem ține cifrele într-un vector de frecvență și să le afișăm crescător, singura diferență fiind faptul că deoarece nu vrem să avem numere care încep cu \(0\), vom afișa cea mai mică cifră nenulă la început. 

#include <fstream>
using namespace std;

ifstream fin("mincifre.in");
ofstream fout("mincifre.out");

int main() {

    char d;
    int fr[10] = {0};

    while (fin >> d) {
        fr[d - '0']++;
    }

    // aflam cea mai mica cifra nenula
    for (int i = 1; i <= 9; i++) {
        if (fr[i] > 0) {
            fout << i;
            fr[i]--;
            break;
        }
    }

    // afisam cifrele in ordine crescatoare
    for (int i = 0; i <= 9; i++) {
        while (fr[i] > 0) {
            fout << i;
            fr[i]--;
        }
    }

    return 0;
}

Problema numere OJI 2005#

Pentru a rezolva această problemă, trebuie să citim cele \(n^2\) valori și să ținem într-un vector de frecvență valorile pe care le-am obținut.

Ulterior, problema se reduce la a afla cel mai mic și cel mai mare număr care nu apare în șir.

Observație

Deși datele de intrare sunt date drept o matrice de dimensiune \(n\), nu trebuie să folosim vreun tablou bidimensional pentru a rezolva această problemă.

#include <fstream>
#include <vector>
using namespace std;

ifstream fin("numere.in");
ofstream fout("numere.out");

int main() {
    int n;
    fin >> n;

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

    int fi = 0, lst = 0;
    for (int i = 1; i <= n * n; i++) {
        if (fr[i] == 0) {
            if(fi == 0) {
                fi = i;
            }
            lst = i;
        }
    }
    fout << fi << " " << lst;
    return 0;
}

Vectori de frecvență dinamici - map și set#

După cum ați observat, vectorii de frecvență au cel mai important rol atunci când vrem să păstrăm valori relativ mici. Dar ce facem atunci când valorile sunt mari?

În acest caz, se impune folosirea unor structuri de date mai avansate, cum ar fi std::map și std::set.

În privința std::map, acesta poate fi folosit în acest context exact ca vectorii de frecvență, având posibilitatea să stocăm dinamic frecvența valorilor care apar, fără a avea nevoie de \(O(valmax)\) memorie. Totuși, această metodă vine cu un cost, și anume faptul că complexitatea operațiilor este \(O(\log n)\), spre deosebire de \(O(1)\) pentru metoda clasică.

În privința std::set, acesta poate fi folosit în acest context exact ca vectorii caracteristici (pentru frecvențe mai mari ca \(1\), std::map este o metodă strict superioară), având posibilitatea să stocăm dinamic valorile care apar, fără a avea nevoie de \(O(valmax)\) memorie. La fel ca la structura de date precedentă, această metodă vine cu un cost, și anume faptul că complexitatea operațiilor este \(O(\log n)\), spre deosebire de \(O(1)\) pentru metoda clasică.

Problema map de pe pbinfo#

#include <map>
#include <fstream>
#include <iostream>

using namespace std;

ifstream fin("map.in");
ofstream fout("map.out");

int n;

map<long long, int> mp;

int main() {
    fin >> n;

    for (int i = 1; i <= n; ++i) {
        long long val;
        fin >> val;
        mp[val]++;
        fout << mp[val] << " ";
    }

    return 0;
}

Concluzii#

Vectorii de frecvență sunt o metodă foarte populară, ce folosește această structură de date cu scopul de a ține memorat numărul de valori egale cu o anumită valoare. Aceștia sunt folositori pentru foarte multe tipuri de probleme și reprezintă parte esențială a altor algoritmi, precum ciurul lui Eratostene.

De asemenea, aceștia se regăsesc frecvent în subiectele de bacalaureat și admitere, mai ales atunci când problemele cer aflarea eficientă a unei soluții care implică optimizări de timp și memorie.

Probleme suplimentare#

Resurse suplimentare#