Vectorul de frecvență

De multe ori nu ne interesează doar dacă o valoare apare, ci de câte ori apare. Pentru a răspunde la această întrebare folosim o variantă a vectorului caracteristic, numită vector de frecvență.

Diferența față de vectorul caracteristic este una singură, dar importantă: în loc să marcăm prezența cu 1, incrementăm poziția corespunzătoare la fiecare apariție. La final, fiecare poziție conține numărul exact de apariții ale valorii respective. Ca și înainte, tehnica este eficientă atunci când valorile urmărite sunt puține și mici, de exemplu cifrele de la 0 la 9.

Enunț. Se citesc n numere naturale. Să se afișeze cel mai mare număr care se poate forma folosind toate cifrele numerelor citite.

#include <iostream>
using namespace std;
int n, f[10];
int main() {
    int x;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> x;
        do {
            f[x % 10]++;
            x /= 10;
        } while (x);
    }
    for (int c = 9; c >= 0; c--)
        for (int j = 1; j <= f[c]; j++)
            cout << c;
    return 0;
}

> 3
> 21 305 12
5322110

> 2
> 90 8
980

Pentru intrarea 3 și numerele 21 305 12 se afișează 5322110, iar pentru 2 și numerele 90 8 se afișează 980.

Pentru fiecare număr citit îi parcurgem cifrele și creștem cu 1 poziția corespunzătoare din vectorul de frecvență f. Extragem cifrele una câte una cu ajutorul operațiilor x % 10 (ultima cifră) și x / 10 (eliminarea ultimei cifre). La final, pentru a obține cel mai mare număr posibil, afișăm cifrele în ordine descrescătoare, fiecare de câte ori apare, adică parcurgem vectorul f de la poziția 9 spre 0.

Am folosit aici o structură repetitivă cu test final (do … while), pentru ca extragerea cifrelor să se execute cel puțin o dată. Astfel, chiar și un număr format dintr-o singură cifră (inclusiv 0) este numărat corect.

Vectorul caracteristic poate fi privit ca un caz particular al vectorului de frecvență, în care ne-am opri la 1. Dacă dintr-un vector de frecvență păstrăm doar informația „zero sau diferit de zero”, obținem exact un vector caracteristic.

Vectorul de frecvență numără aparițiile unor valori, incrementând câte o poziție dedicată fiecărei valori. Este una dintre cele mai utile tehnici pentru problemele cu cifre și pentru numărarea rapidă a unor elemente, evitând parcurgeri repetate ale datelor. Împreună cu vectorul caracteristic, încheie setul de tehnici fundamentale de lucru cu tablourile unidimensionale.