어레이 C++에서 가장 빈번한 요소 찾기

Jinku Hu 2023년10월12일
  1. 반복 방법과 함께std::sort알고리즘을 사용하여 배열에서 가장 빈번한 요소 찾기
  2. std::unorder_map컨테이너를std::max_element함수와 함께 사용하여 배열에서 가장 빈번한 요소 찾기
어레이 C++에서 가장 빈번한 요소 찾기

이 기사는 배열 C++에서 가장 빈번한 요소를 찾는 방법에 대한 여러 가지 방법을 보여줍니다.

반복 방법과 함께std::sort알고리즘을 사용하여 배열에서 가장 빈번한 요소 찾기

배열에서 가장 빈번한 요소를 찾는 일반적인 해결책은 정렬 된 배열 버전을 탐색하고 요소 빈도 수를 유지하는 것입니다. 이 경우 배열이 정수 시퀀스이고std::vector컨테이너에 저장된다고 가정합니다.

처음에는std::sort알고리즘을 사용하여 정수 배열을 정렬하여 가장 빈번한 요소를 찾기에 충분한 일회성 순회를 만들어야합니다. 반복하는 동안 여러 변수가 필요합니다. 즉, 현재 요소와 비교할 마지막 반복의 정수를 저장합니다. 또한 루프의 각주기에서 가장 자주 업데이트되는 정수 값을 유지합니다. 알고리즘은 현재 요소가 이전 요소와 같은지 확인하고 표현식이 참일 때 주파수 카운터를 증가시킵니다. 참이 아닌 경우 현재 주파수 수가 지금까지 발생한 최대 값보다 큰지 확인하고, 그렇다면 최대 주파수 수와 가장 빈번한 요소에 대한 업데이트 된 값을 저장합니다.

그런 다음 이전 정수 변수를 수정하고 현재 주파수를1로 재설정합니다. 루프가 완료되면 현재 주파수와 최대 주파수를 비교하는if조건이 하나 더 있습니다. 그러면 결과 요소를 식별 할 수 있습니다.

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

출력:

Most frequent element = 10

std::unorder_map컨테이너를std::max_element함수와 함께 사용하여 배열에서 가장 빈번한 요소 찾기

또는std::unordered_map클래스를 사용하여 각 요소에 대한 빈도를 축적 한 다음std::max_element알고리즘을 호출하여 가장 큰 값을 가진 요소를 식별 할 수 있습니다. 주파수를 누적하려면 전체 배열을 순회하고 매 반복마다 맵에 삽입해야합니다. 이 경우std::max_element메소드는 세 개의 인수, 처음 두 개 (범위 시작 및 종료 지정자)를 사용합니다. 세 번째 인수는std::pair유형 인std::unordered_map의 요소를 비교하는 람다 함수입니다. 마지막으로 반환 된max_element알고리즘 쌍에서 두 번째 항목을 반환 할 수 있습니다.

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

출력:

Most frequent element = 10
작가: Jinku Hu
Jinku Hu avatar Jinku Hu avatar

Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.

LinkedIn Facebook

관련 문장 - C++ Array