Clasa a IX-a · Frecvență, sume parțiale și ciurul lui EratosteneRead in English

Vectorul de frecvență în C++

În engleză: Frequency array

O(n)C++1743 de linii1 exemplu

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

Exemplul 1

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.

vector-de-frecventa.cpp
/*
 * 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.