Häufigstes Element in einem Array finden C++

1. Verwenden Sie den Algorithmus std::sort mit iterativer Methode, um das häufigste Element in einem Array zu finden
2. Verwenden Sie den Container std::unordered_map mit der Funktion std::max_element, um das häufigste Element in einem Array zu finden

Dieser Artikel zeigt verschiedene Methoden zum Auffinden des häufigsten Elements in einem Array C++.

Verwenden Sie den Algorithmus std::sort mit iterativer Methode, um das häufigste Element in einem Array zu finden

Die einfache Lösung, um das häufigste Element in einem Array zu finden, besteht darin, die sortierte Version des Arrays zu durchlaufen und die Anzahl der Elementfrequenzen beizubehalten. In diesem Fall nehmen wir an, dass das Array eine Folge von Ganzzahlen ist und diese in einem std::vector-Container gespeichert sind.

Zuerst müssen wir das Array von Ganzzahlen mit dem Algorithmus std::sort sortieren, sodass eine einmalige Durchquerung ausreicht, um das häufigste Element zu finden. Beachten Sie, dass wir während der Iteration mehrere Variablen benötigen. Wir speichern nämlich die Ganzzahl aus der letzten Iteration, um sie mit dem aktuellen Element zu vergleichen. Außerdem halten wir den Wert der häufigsten Ganzzahl in jedem Zyklus der Schleife auf dem neuesten Stand. Der Algorithmus prüft, ob das aktuelle Element dem vorherigen entspricht, und erhöht den Frequenzzähler, wenn der Ausdruck wahr ist. Wenn dies nicht der Fall ist, prüfen wir, ob die aktuelle Frequenzanzahl größer als das bisher festgestellte Maximum ist, und speichern in diesem Fall die aktualisierten Werte für die maximale Frequenzanzahl und das häufigste Element.

Dann ändern wir die vorherige Ganzzahlvariable und setzen die aktuelle Frequenz auf 1 zurück. Sobald die Schleife beendet ist, gibt es eine weitere if-Bedingung, um aktuelle und maximale Frequenzen zu vergleichen, und dann können wir das Ergebniselement identifizieren.

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

Ausgabe:

Most frequent element = 10

Verwenden Sie den Container std::unordered_map mit der Funktion std::max_element, um das häufigste Element in einem Array zu finden

Alternativ können wir die Klasse std::unordered_map verwenden, um Frequenzen für jedes Element zu akkumulieren, und dann den Algorithmus std::max_element aufrufen, um das Element mit dem größten Wert zu identifizieren. Beachten Sie, dass das Akkumulieren von Frequenzen das Durchlaufen des gesamten Arrays und das Einfügen jeder Iteration in die Karte erfordert. In diesem Fall verwendet die Methode std::max_element drei Argumente, die ersten beiden: die Anfangs- und Endspezifizierer des Bereichs. Das dritte Argument ist die Lambda-Funktion zum Vergleichen der Elemente der std::unordered_map vom Typ std::pair. Schließlich können wir das zweite Element aus dem zurückgegebenen Paaralgorithmus max_element zurückgeben.

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

Ausgabe:

Most frequent element = 10