Vectori de frecvență și vectori caracteristici

Un vector de frecvență memorează de câte ori apare fiecare valoare. Indicele reprezintă valoarea, iar elementul stocat reprezintă numărul ei de apariții. Un vector caracteristic păstrează numai prezența: zero pentru absent și unu pentru prezent.

Metoda este potrivită când valorile aparțin unui domeniu mic și ordinea lor inițială nu este necesară. Nu este o altă denumire pentru vectorul de intrare. Transformarea pierde informația despre poziții, deci nu poate răspunde singură la întrebări despre vecini sau secvențe consecutive.

Cum funcționează

Pentru valori între 0 și M, rezervăm M+1 poziții și le inițializăm cu zero. La citirea lui x executăm ++f[x]. După prelucrare, f[7] indică numărul aparițiilor valorii 7, nu al șaptelea număr citit. Dacă vrem doar prezența, atribuim unu în loc să incrementăm.

Pentru a găsi cea mai frecventă valoare, parcurgem domeniul. Stabilim explicit departajarea: la frecvențe egale păstrăm valoarea mai mică. O parcurgere crescătoare și actualizarea numai la frecvență strict mai mare realizează această regulă. Afișarea valorilor în ordine poate fi obținută repetând fiecare indice de f[x] ori.

Valorile negative pot fi deplasate cu o constantă dacă intervalul total rămâne mic. Pentru numere rare dintr-un domeniu enorm, un tablou direct ar consuma inutil memorie. Atunci luăm în calcul sortarea, comprimarea coordonatelor sau un dicționar. Alegerea structurii pornește din restricțiile problemei, nu din preferința pentru un anumit container.

Exemplu urmărit pas cu pas

Pentru 4, 2, 4, 0, 2 avem f[0]=1, f[2]=2 și f[4]=2. Celelalte poziții rămân zero. Valoarea dominantă este 2, deoarece ea și 4 au frecvența doi, iar departajarea cere minimul. Vectorul caracteristic ar păstra doar indicii 0, 2 și 4 ca prezenți și ar pierde informația despre egalitatea frecvențelor.

Programul presupune 1 <= n <= 100000 și valori între 0 și 100. Tabloul are 101 poziții deoarece și zero este permis. Varianta cu vector păstrează aceeași indexare directă și aceeași inițializare.

Implementare C++17

Varianta cu tablou clasic:

#include <iostream>
int main() {
    int n, f[101] = {};
    std::cin >> n;
    for (int i = 0; i < n; ++i) {
        int x;
        std::cin >> x;
        ++f[x];
    }
    int best = 0;
    for (int x = 1; x <= 100; ++x)
        if (f[x] > f[best])
            best = x;
    std::cout << best << ' ' << f[best] << '\n';
}

Varianta echivalentă cu std::vector folosește aceleași limite și aceiași indici:

#include <iostream>
#include <vector>
int main() {
    int n;
    std::vector<int> f(101, 0);
    std::cin >> n;
    for (int i = 0; i < n; ++i) {
        int x;
        std::cin >> x;
        ++f[x];
    }
    int best = 0;
    for (int x = 1; x <= 100; ++x)
        if (f[x] > f[best])
            best = x;
    std::cout << best << ' ' << f[best] << '\n';
}

De ce funcționează și cât costă

După primele k citiri, fiecare f[x] numără exact aparițiile lui x în acel prefix. Actualizarea unei singure poziții păstrează afirmația. Căutarea maximului examinează toate valorile posibile și regula strictă păstrează cea mai mică valoare dintre cele aflate la egalitate.

Timpul este O(n+M), iar memoria O(M), unde M este valoarea maximă admisă. Nu scriem doar O(n), deoarece parcurgerea domeniului poate domina atunci când n este mic.

Greșeli frecvente

Nu declara frecvențele fără inițializare și nu indexa cu valori nevalidate din afara domeniului. Dacă problema permite un șir gol, trebuie definit separat ce înseamnă valoare dominantă; programul nostru presupune un șir nevid.

Exersează

Determină numărul valorilor distincte și numărul valorilor care apar exact de două ori în exemplul de mai sus.

Rezolvare explicată: Sunt trei valori distincte, deoarece trei poziții au frecvență nenulă. Două valori, 2 și 4, au frecvența exact doi; numărăm pozițiile, nu suma frecvențelor.

Continuă să înveți

Parcurgerea vectorilor, sortare și căutare.

Întrebări frecvente

Ce memorează f[x]?

Într-un vector de frecvență, f[x] memorează numărul aparițiilor valorii x. Indicele codifică valoarea, nu poziția ei în șirul de intrare.

Cum diferă vectorul caracteristic?

Vectorul caracteristic arată doar dacă o valoare apare cel puțin o dată. Frecvența păstrează și numărul aparițiilor, deci permite identificarea duplicatelor și a valorii dominante.

Pot folosi frecvențe pentru valori negative?

Da, dacă domeniul este mic, deplasezi indicii cu o constantă. De exemplu, valorile din [-50,50] pot fi memorate la indicii 0 până la 100.

De ce nu folosesc frecvențe pentru valori până la un miliard?

Un tablou cu peste un miliard de poziții poate depăși memoria disponibilă. Pentru puține valori distincte, sortarea sau un dicționar folosesc mai potrivit resursele.

Mai pot reconstrui ordinea inițială?

Nu din frecvențe singure. Șirurile 1,2,1 și 1,1,2 au aceleași frecvențe. Dacă pozițiile contează, trebuie să păstrezi suplimentar datele de intrare.