Encuentre el elemento más frecuente en un array C++

1. Utilice el algoritmo std::sort con el método iterativo para encontrar el elemento más frecuente en un array
2. Utilice el contenedor std::unordered_map con la función std::max_element para encontrar el elemento más frecuente en un array

Este artículo demostrará varios métodos sobre cómo encontrar el elemento más frecuente en un array C++.

Utilice el algoritmo std::sort con el método iterativo para encontrar el elemento más frecuente en un array

La solución simple para encontrar el elemento más frecuente en un array es atravesar la versión ordenada del array y mantener recuentos de frecuencias de elementos. En este caso, asumimos que el array es una secuencia de números enteros y están almacenados en un contenedor std::vector.

Al principio, necesitamos ordenar el array de enteros usando el algoritmo std::sort, haciendo que el recorrido de una sola vez sea suficiente para encontrar el elemento más frecuente. Tenga en cuenta que necesitamos varias variables durante la iteración. Es decir, almacenamos el número entero de la última iteración para compararlo con el elemento actual; Además, mantenemos actualizado el valor del número entero más frecuente en cada bucle del bucle. El algoritmo verifica si el elemento actual es igual al anterior e incrementa el contador de frecuencia cuando la expresión es verdadera. Cuando no es cierto, verificamos si el recuento de frecuencia actual es mayor que el máximo encontrado hasta ahora, y si es así, almacenamos los valores actualizados para el recuento de frecuencia máxima y el elemento más frecuente.

Luego modificamos la variable entera anterior y restablecemos la frecuencia actual a 1. Una vez que finaliza el bucle, hay una condición if más para comparar las frecuencias actuales y máximas, y luego podemos identificar el elemento de resultado.

#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);
}

Producción :

Most frequent element = 10

Utilice el contenedor std::unordered_map con la función std::max_element para encontrar el elemento más frecuente en un array

Alternativamente, podemos utilizar la clase std::unordered_map para acumular frecuencias para cada elemento y luego llamar al algoritmo std::max_element para identificar el elemento con el mayor valor. Tenga en cuenta que la acumulación de frecuencias requiere un recorrido de toda el array e insertar en el mapa cada iteración. En este caso, el método std::max_element toma tres argumentos, los dos primeros: los especificadores de inicio y final de rango. El tercer argumento es la función lambda para comparar los elementos del std::unordered_map, que son del tipo std::pair. Finalmente, podemos devolver el segundo elemento del par algoritmo max_element devuelto.

#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);
}

Producción :

Most frequent element = 10