Clasa a IX-a · Frecvență, sume parțiale și ciurul lui EratosteneRead in English
Vectorul de frecvență în C++
În engleză: Frequency array
Ideea
Pentru valori naturale mici (aici 0..1000), frecv[x] reține de câte ori a apărut valoarea x. Valoarea devine indice, așa că fiecare număr citit se numără într-un singur pas. La final aflăm valoarea care apare cel mai des (cea mai mică, la egalitate) și frecvența ei.
Descrierea în engleză
For small natural values (here 0..1000), frecv[x] stores how many times the value x has appeared. The value becomes an index, so every number read is counted in a single step. At the end we find the most frequent value (the smallest one, on ties) and its frequency.
- Complexitate
- O(n + V), unde V este valoarea maximă posibilă
- Clasa
- Clasa a IX-a (Grade 9)
Exemple
Intrare
8 3 7 3 1 7 3 9 1
Ieșire așteptată
3 3
Codul C++
Codul complet, cu comentarii în română. Îl poți modifica liber și îl poți reseta oricând.
/*
* Titlu: Vectorul de frecvență
* Clasa: 9
* Capitol: Frecvență, sume parțiale și ciurul lui Eratostene
* Descriere: Pentru valori naturale mici (aici 0..1000), frecv[x] reține de câte
* ori a apărut valoarea x. Valoarea devine indice, așa că fiecare
* număr citit se numără într-un singur pas. La final aflăm valoarea
* care apare cel mai des (cea mai mică, la egalitate) și frecvența ei.
* Complexitate: O(n + V), unde V este valoarea maximă posibilă
*
* Exemplu
* Intrare:
* 8
* 3 7 3 1 7 3 9 1
* Ieșire: 3 3
*/
#include <iostream>
using namespace std;
const int VMAX = 1000;
int frecv[VMAX + 1];
int main()
{
int n, x;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> x;
frecv[x]++;
}
int valoare = 0;
for (int val = 1; val <= VMAX; val++)
{
if (frecv[val] > frecv[valoare])
{
valoare = val;
}
}
cout << valoare << ' ' << frecv[valoare] << '\n';
return 0;
}
Rulează pe un g++ adevărat (C++17, -O2) prin Compiler Explorer. Programele trebuie să se termine repede: există o limită de timp.