Trova l'elemento più frequente in un array C++

1. Usa l’algoritmo std::sort con il metodo iterativo per trovare l’elemento più frequente in un array
2. Usa il contenitore std::unordered_map con la funzione std::max_element per trovare l’elemento più frequente in un array

Questo articolo illustrerà più metodi su come trovare l’elemento più frequente in una matrice C++.

Usa l’algoritmo std::sort con il metodo iterativo per trovare l’elemento più frequente in un array

La soluzione semplice per trovare l’elemento più frequente in un array è attraversare la versione ordinata dell’array e mantenere il conteggio delle frequenze degli elementi. In questo caso, assumiamo che l’array sia una sequenza di numeri interi e che siano memorizzati in un contenitore std::vector.

All’inizio, abbiamo bisogno di ordinare l’array di numeri interi usando l’algoritmo std::sort, rendendo sufficiente un attraversamento una tantum per trovare l’elemento più frequente. Nota che abbiamo bisogno di diverse variabili durante l’iterazione. Vale a dire, memorizziamo il numero intero dall’ultima iterazione per confrontarlo con l’elemento corrente; inoltre, manteniamo aggiornato il valore dell’intero più frequente ad ogni bucle del bucle. L’algoritmo controlla se l’elemento corrente è uguale a quello precedente e incrementa il frequenzimetro quando l’espressione è vera. Quando non è vero, controlliamo se il conteggio della frequenza corrente è maggiore del massimo incontrato finora e, in tal caso, memorizziamo i valori aggiornati per il conteggio della frequenza massima e l’elemento più frequente.

Quindi modifichiamo la variabile intera precedente e reimpostiamo la frequenza corrente su 1. Una volta terminato il bucle, c’è un’altra condizione if per confrontare le frequenze correnti e massime, e quindi possiamo identificare l’elemento risultato.

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

Produzione:

Most frequent element = 10

Usa il contenitore std::unordered_map con la funzione std::max_element per trovare l’elemento più frequente in un array

In alternativa, possiamo utilizzare la classe std::unordered_map per accumulare frequenze per ogni elemento e quindi chiamare l’algoritmo std::max_element per identificare l’elemento con il valore più grande. Notare che l’accumulo di frequenze richiede un attraversamento dell’intero array e l’inserimento nella mappa di ogni iterazione. In questo caso, il metodo std::max_element accetta tre argomenti, i primi due: gli specificatori di inizio e di fine dell’intervallo. Il terzo argomento è la funzione lambda per confrontare gli elementi di std::unordered_map, che sono di tipo std::pair. Infine, possiamo restituire il secondo elemento dall’algoritmo di coppia max_element restituito.

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

Produzione:

Most frequent element = 10