Rechercher l'élément le plus fréquent dans un tableau C++

1. Utilisez l’algorithme std::sort avec la méthode itérative pour trouver l’élément le plus fréquent dans un tableau
2. Utilisez le conteneur std::unordered_map avec la fonction std::max_element pour trouver l’élément le plus fréquent dans un tableau

Cet article présente plusieurs méthodes expliquant comment rechercher l’élément le plus fréquent dans un tableau C++.

Utilisez l’algorithme std::sort avec la méthode itérative pour trouver l’élément le plus fréquent dans un tableau

La solution simple pour trouver l’élément le plus fréquent dans un tableau est de parcourir la version triée du tableau et de garder le décompte des fréquences des éléments. Dans ce cas, nous supposons que le tableau est une suite d’entiers, et ils sont stockés dans un conteneur std::vector.

Dans un premier temps, nous devons trier le tableau d’entiers en utilisant l’algorithme std::sort, en faisant un parcours unique suffisant pour trouver l’élément le plus fréquent. Notez que nous avons besoin de plusieurs variables lors de l’itération. À savoir, nous stockons l’entier de la dernière itération pour le comparer à l’élément courant; aussi, nous gardons la valeur de l’entier le plus fréquent mis à jour à chaque cycle de la boucle. L’algorithme vérifie si l’élément courant est égal au précédent et incrémente le compteur de fréquence lorsque l’expression est vraie. Lorsque ce n’est pas vrai, nous vérifions si le nombre de fréquences actuel est supérieur au maximum rencontré jusqu’à présent, et si tel est le cas, nous stockons les valeurs mises à jour pour le nombre de fréquences maximum et l’élément le plus fréquent.

Ensuite, nous modifions la variable entière précédente et remettons la fréquence actuelle à 1. Une fois la boucle terminée, il y a encore une condition if pour comparer les fréquences actuelles et maximales, puis nous pouvons identifier l’élément de résultat.

#include <iostream>
#include <string>
#include <vector>

using std::cin;
using std::cout;
using std::endl;
using std::sort;
using std::vector;

int getMostFrequentElement(vector<int> &arr) {
  if (arr.empty()) return -1;

  sort(arr.begin(), arr.end());

  auto last_int = arr.front();
  auto most_freq_int = arr.front();
  int max_freq = 0, current_freq = 0;

  for (const auto &i : arr) {
    if (i == last_int)
      ++current_freq;
    else {
      if (current_freq > max_freq) {
        max_freq = current_freq;
        most_freq_int = last_int;
      }

      last_int = i;
      current_freq = 1;
    }
  }

  if (current_freq > max_freq) {
    max_freq = current_freq;
    most_freq_int = last_int;
  }

  return most_freq_int;
}

int main() {
  vector<int> arr = {1, 2, 3, 4,  5,  6, 7, 8, 9, 10, 2, 3, 4, 5,  6,
                     7, 8, 9, 10, 10, 2, 3, 4, 5, 6,  7, 8, 9, 10, 10};

  int ret = getMostFrequentElement(arr);
  if (ret == -1) {
    perror("getMostFrequentElement");
    exit(EXIT_FAILURE);
  }
  cout << "Most frequent element = " << ret << endl;

  exit(EXIT_SUCCESS);
}

Production:

Most frequent element = 10

Utilisez le conteneur std::unordered_map avec la fonction std::max_element pour trouver l’élément le plus fréquent dans un tableau

Alternativement, nous pouvons utiliser la classe std::unordered_map pour accumuler les fréquences pour chaque élément puis appeler l’algorithme std::max_element pour identifier l’élément avec la plus grande valeur. Notez que l’accumulation de fréquences nécessite une traversée de l’ensemble du tableau et l’insertion dans la carte à chaque itération. Dans ce cas, la méthode std::max_element prend trois arguments, les deux premiers: les spécificateurs de début et de fin de la plage. Le troisième argument est la fonction lambda pour comparer les éléments de std::unordered_map, qui sont de type std::pair. Enfin, nous pouvons renvoyer le deuxième item de l’algorithme du couple max_element retourné.

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>

using std::cin;
using std::cout;
using std::endl;
using std::sort;
using std::unordered_map;
using std::vector;

int getMostFrequentElement(vector<int> &arr) {
  if (arr.empty()) return -1;

  unordered_map<int, int> freq_count;

  for (const auto &item : arr) freq_count[item]++;

  auto most_freq_int = std::max_element(
      freq_count.begin(), freq_count.end(),
      [](const auto &x, const auto &y) { return x.second < y.second; });

  return most_freq_int->first;
}

int main() {
  vector<int> arr = {1, 2, 3, 4,  5,  6, 7, 8, 9, 10, 2, 3, 4, 5,  6,
                     7, 8, 9, 10, 10, 2, 3, 4, 5, 6,  7, 8, 9, 10, 10};

  int ret = getMostFrequentElement(arr);
  if (ret == -1) {
    perror("getMostFrequentElement");
    exit(EXIT_FAILURE);
  }
  cout << "Most frequent element = " << ret << endl;

  exit(EXIT_SUCCESS);
}

Production:

Most frequent element = 10