Cel mai frecvent element dintr-un șir în C++

Dându-se un șir de numere naturale a[] de lungime n, să se determine numărul care apare de cele mai multe ori în șir (în caz de egalitate, considerăm numărul mai mic).

Considerăm că atât n, cât și elementele șirului sunt mai mici decât 1000.

Exemplu. Pentru șirul a = (1, 10, 1, 1, 9, 7, 4, 10), răspunsul este 1, deoarece apare de cele mai multe ori.

Metoda 1: Vector de frecvență

O metodă ar fi să ne folosim de un vector de frecvență. Vom crea un vector, fr, inițial gol, în care fr[i] reprezintă numărul de apariții ale lui i în șirul a. Spre exemplu, în exemplul de mai sus, fr[1] = 3, iar fr[10] = 2.

Pentru a forma acest vector, parcurgem elementele șirului și le marcăm în fr, pe rând.

La final, parcurgem toate elementele posibile din fr, verificând care apare de cele mai multe ori.

Implementare C++

#include <iostream>

using namespace std;

int main()
{
    //Declarăm și citim șirul nostru
    int n, a[1001];
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    //Declarăm și calculăm vectorul de frecvență
    int fr[1001];
    for(int i = 1; i <= 1000; i++) { //Vectorul trebuie golit la început
        fr[i] = 0;
    }
    for(int i = 1; i <= n; i++) {
        fr[a[i]]++; //Valoarea elementului curent este a[i]. Așadar, creștem frecvența acesteia
    }
    int valMax = 1;
    for(int i = 1; i <= 1000; i++) {
        if(fr[valMax] < fr[i]) { //Frecvența numărului cu număr maxim de apariții nu este maximul => îl schimbăm
            valMax = i;
        }
    }

    //Afișăm răspunsul
    cout << "Numărul " << valMax << " apare de " << fr[valMax] << " ori (maxim posibil)";
    return 0;
}

Metoda 2: Sortare

Sortăm vectorul nostru. Din vectorul sortat, elementele egale sunt consecutive, așadar trebuie să determinăm cea mai lungă secvență de elemente consecutive.

Pentru sortare, vom folosi Bubble sort, un algoritm clasic de sortare.

Implementare C++

#include <iostream>

using namespace std;

int main()
{
    //Declarăm și citim șirul nostru
    int n, a[1001];
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    //Sortăm șirul a
    for(int i = 1; i < n; i++) {
        for(int j = i + 1; j <= n; j++) {
            if(a[i] > a[j]) {
                int aux = a[i];
                a[i] = a[j];
                a[j] = aux;
            }
        }
    }

    //Determinăm secvența cu număr maxim de elemente egale
    int valMax = 0, valMaxFr = 0; //Valoarea maximă și frecvența ei
    int valCrt = 0, valCrtFr = 0; //Valoarea curentă și frecvența ei
    for(int i = 1; i <= n; i++) {
        if(a[i] == a[i - 1]) {
            valCrtFr++;
        } else {
            if(valCrtFr > valMaxFr) { //Am găsit un nou maxim, actualizăm variabilele
                valMax = valCrt;
                valMaxFr = valCrtFr;
            }
            //Formăm o nouă secvență: are lungimea 1 și valoarea a[i]
            valCrt = a[i];
            valCrtFr = 1;
        }
    }

    //Afișăm răspunsul
    cout << "Numărul " << valMax << " apare de " << valMaxFr << " ori (maxim posibil)";
    return 0;
}