Encontre o elemento mais frequente em um array C++

1. Use o algoritmo std::sort com método iterativo para encontrar o elemento mais frequente em um array
2. Use o recipiente std::unordered_map com a função std::max_element para localizar o elemento mais frequente em um array

Este artigo demonstrará vários métodos sobre como localizar o elemento mais frequente em um array C++.

Use o algoritmo std::sort com método iterativo para encontrar o elemento mais frequente em um array

A solução simples para encontrar o elemento mais frequente em um array é percorrer a versão classificada do array e manter contagens das frequências dos elementos. Neste caso, assumimos que o array é uma sequência de inteiros, e eles são armazenados em um contêiner std::vector.

Em primeiro lugar, precisamos classificar o array de inteiros usando o algoritmo std::sort, tornando a travessia única suficiente para encontrar o elemento mais frequente. Observe que precisamos de várias variáveis ​​durante a iteração. Ou seja, armazenamos o inteiro da última iteração para comparar com o elemento atual; além disso, mantemos o valor do número inteiro mais frequente atualizado em cada bucle do loop. O algoritmo verifica se o elemento atual é igual ao anterior e incrementa o contador de frequência quando a expressão é verdadeira. Quando não é verdade, verificamos se a contagem de frequência atual é maior que o máximo encontrado até agora e, em caso afirmativo, armazenamos os valores atualizados para a contagem de frequência máxima e o elemento mais frequente.

Em seguida, modificamos a variável inteira anterior e redefinimos a frequência atual para 1. Uma vez que o loop termina, há mais uma condição if para comparar as frequências atuais e máximas, e então podemos identificar o 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);
}

Resultado:

Most frequent element = 10

Use o recipiente std::unordered_map com a função std::max_element para localizar o elemento mais frequente em um array

Alternativamente, podemos utilizar a classe std::unordered_map para acumular frequências para cada elemento e então chamar o algoritmo std::max_element para identificar o elemento com o maior valor. Observe que o acúmulo de frequências requer uma travessia de toda a matriz e a inserção no mapa de cada iteração. Neste caso, o método std::max_element leva três argumentos, os dois primeiros: os especificadores de início e fim do intervalo. O terceiro argumento é a função lambda para comparar os elementos do std::unordered_map, que são do tipo std::pair. Finalmente, podemos retornar o segundo item do algoritmo de par max_element retornado.

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

Resultado:

Most frequent element = 10