Vectorul de frecvență la BAC: numărări în C++

Un vector de frecvență memorează de câte ori apare fiecare valoare dintr-un domeniu mic și cunoscut. Indicele reprezintă valoarea căutată, iar elementul de la acel indice reprezintă numărul aparițiilor ei. La BAC, această tehnică simplifică probleme despre valori distincte, repetări, cea mai frecventă valoare sau egalitatea a două colecții de elemente.

Metoda este potrivită când valorile pot fi folosite ca indici fără să ceară un tablou exagerat de mare. În această lecție folosim valori naturale între zero și o sută inclusiv. Limitele sunt parte din alegerea algoritmului, la fel ca în subiectele de BAC la informatică.

Diferența dintre vectorul inițial și vectorul de frecvență

Considerăm secvența patru, unu, patru, zero, unu, patru. În vectorul inițial, indicele arată poziția unui element. În vectorul de frecvență, indicele patru arată câte valori egale cu patru există în întreaga secvență.

Valoare	Frecvență	Interpretare
0	1	Zero apare o dată
1	2	Unu apare de două ori
2	0	Doi nu apare
3	0	Trei nu apare
4	3	Patru apare de trei ori

Suma frecvențelor este șase, egală cu numărul elementelor citite. Numărul valorilor distincte este trei, deoarece trei poziții ale vectorului de frecvență au valori strict pozitive. Aceste două rezultate se obțin din aceeași structură, dar prin operații diferite.

Nu confunda frecvența maximă, care este trei, cu valoarea cea mai frecventă, care este patru. Cerința poate solicita una dintre ele sau ambele. Numele variabilelor ar trebui să păstreze această diferență clară.

Inițializarea tuturor frecvențelor cu zero

Înainte de citirea datelor, nicio valoare nu a fost întâlnită. Prin urmare, fiecare frecvență trebuie să fie zero. Un tablou local neinițializat nu oferă această garanție. Valorile sale nu pot fi tratate ca niște contoare corecte.

În C++, declarația cu inițializator gol folosită în programul de mai jos pune toate elementele tabloului la zero. Apoi, pentru fiecare valoare citită, mărești exact frecvența de la indicele egal cu acea valoare.

Dacă citești valoarea patru, mărești frecvența lui patru cu unu. Nu pui frecvența la patru și nu mărești un element ales după poziția curentă din secvență. Indicele vectorului de frecvență vine din valoarea citită.

Construirea structurii fără memorarea secvenței

Dacă toate cerințele privesc doar numărul aparițiilor, poți actualiza frecvențele chiar la citire. Nu mai este necesar un tablou separat cu ordinea originală a elementelor.

Pentru secvența exemplului, după primele două valori ai câte o apariție pentru patru și unu. După a treia valoare, frecvența lui patru devine doi. La final, vectorul rezumă distribuția valorilor, dar nu mai spune în ce ordine au apărut.

Această pierdere a ordinii este intenționată. Dacă se cere ulterior prima poziție a unei valori sau lungimea unei secvențe de elemente consecutive, frecvențele singure nu sunt suficiente. Alege structura după informația de care ai nevoie la final.

Program C++ pentru valori distincte și cea mai frecventă valoare

Programul citește între unu și o sută de mii de elemente, fiecare între zero și o sută. Afișează numărul valorilor distincte, apoi cea mai mică valoare dintre cele cu frecvență maximă și frecvența ei.

#include <iostream>
using namespace std;

int main() {
    int n, x, f[101] = {};
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> x;
        ++f[x];
    }
    int distincte = 0;
    int valoare = 0, frecventaMaxima = 0;
    for (int v = 0; v <= 100; ++v) {
        if (f[v] > 0) ++distincte;
        if (f[v] > frecventaMaxima) {
            frecventaMaxima = f[v];
            valoare = v;
        }
    }
    cout << distincte << '\n';
    cout << valoare << ' ' << frecventaMaxima;
    return 0;
}

Parcurgerea valorilor este crescătoare, iar actualizarea folosește o comparație strictă. De aceea, la egalitate de frecvență, rămâne prima valoare întâlnită, adică cea mai mică. Dacă ai actualiza și la egalitate, ai păstra cea mai mare dintre valorile cu frecvență maximă.

Șirul este nevid, deci frecvența maximă devine pozitivă. Inițializarea valorii candidate cu zero nu afirmă că zero apare obligatoriu: primul element cu frecvență pozitivă va înlocui candidatul, dacă este necesar.

Timpul depinde de lungime și de domeniu

Construirea frecvențelor necesită o parcurgere a datelor. Apoi parcurgi domeniul valorilor posibile. Pentru un domeniu de dimensiune cunoscută, timpul este proporțional cu numărul elementelor plus dimensiunea domeniului.

Memoria pentru frecvențe este proporțională cu dimensiunea domeniului, nu cu numărul elementelor citite. În exemplul nostru, ai nevoie de 101 contoare, chiar dacă citești o sută de mii de valori. Dar dacă valorile ar ajunge la un miliard, un tablou cu câte o poziție pentru fiecare valoare ar deveni nepractic.

Nu folosi vectorul de frecvență fără să citești limitele. O tehnică eficientă pentru cifre sau valori mici poate fi nepotrivită pentru un domeniu foarte mare și rar ocupat. Alte metode, precum sortarea, pot deveni mai potrivite, în funcție de cerință și de structurile permise.

Valori negative și deplasarea indicilor

Un indice negativ nu este valid pentru tabloul obișnuit. Dacă domeniul este, de exemplu, de la minus zece la zece, poți transforma valoarea într-un indice adăugând zece. Astfel, minus zece ajunge la indicele zero, zero la indicele zece, iar zece la indicele douăzeci.

La interpretarea rezultatelor, aplici transformarea inversă: scazi zece din indice pentru a recupera valoarea. Trebuie rezervate 21 de poziții, deoarece ambele capete ale intervalului sunt incluse.

Această tehnică nu schimbă frecvențele, ci doar modul de adresare. Scrie un tabel cu valorile de la capete și cu zero pentru a verifica deplasarea. Este o aplicare practică a învățării prin înțelegere: justifici formula indicelui printr-o corespondență clară.

Ce alte cerințe poți rezolva

O valoare apare exact o dată dacă frecvența ei este unu. O valoare lipsește dacă frecvența este zero. Numărul aparițiilor unor valori dintr-un interval se obține adunând frecvențele corespunzătoare, nu doar numărând pozițiile nenule.

Două secvențe au aceleași valori cu aceleași multiplicități dacă vectorii lor de frecvență coincid pe întregul domeniu. Această condiție nu spune că ordinea este aceeași. Secvențele unu, doi, unu și unu, unu, doi au aceleași frecvențe, dar ordini diferite.

Poți reconstrui și lista sortată crescător: parcurgi valorile în ordine și afișezi fiecare valoare de atâtea ori cât arată frecvența. Această operație reface multiplicitățile, însă nu poate recupera ordinea inițială pierdută.

Exerciții cu răspunsuri

Pentru doi, cinci, doi, cinci, unu, sunt trei valori distincte. Frecvența maximă este doi, iar cea mai mică valoare care o atinge este doi. Regula de departajare trebuie menționată în răspuns.

Pentru zero, zero, zero, există o singură valoare distinctă. Valoarea cea mai frecventă este zero și apare de trei ori. Acest test verifică dacă ai inclus indicele zero în parcurgere.

Pentru unu, trei, trei, patru, câte elemente au valori între doi și patru inclusiv? Trei elemente: cele două apariții ale lui trei și apariția lui patru. Numărul valorilor distincte din interval este însă doi.

Întrebări frecvente

De ce tabloul are 101 poziții pentru valori până la o sută?

Fiindcă domeniul include și zero. Indicii de la zero la o sută reprezintă 101 valori posibile, nu o sută.

Pot determina prima poziție doar din frecvențe?

Nu. Structura reține câte apariții există, nu unde se află ele. Pentru poziții, trebuie păstrată informație suplimentară în timpul citirii.

Cum îmi verific rezultatul?

Adună frecvențele și compară suma cu numărul elementelor. Testează zero, valoarea maximă permisă și o egalitate între frecvențe. Dacă încă le confunzi cu pozițiile, poți exersa pe tabele la meditații de informatică.