C++의 다수 요소 II

하나의 정수 배열이 있다고 가정합니다. 우리는 n/3의 바닥보다 더 많이 나타나는 요소를 찾아야 합니다. 여기서 n은 배열의 크기입니다.

따라서 입력이 [1,1,1,3,3,2,2,2]와 같으면 결과는 [1,2]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 첫 번째 :=0, 두 번째 :=1, cnt1 :=0, cnt2 :=0, n :=배열 수의 크기

• 범위 0에서 n – 1까지의 i에 대해

  • x :=숫자[i]

  • x가 첫 번째이면 cnt를 1만큼 증가,

  • 그렇지 않으면 x가 두 번째일 때 cnt2를 1 증가시킵니다.

  • 그렇지 않으면 cnt1이 0이면 먼저 x로 설정하고 cnt1 :=1

  • 그렇지 않으면 cnt2가 0이면 초를 x로 설정하고 cnt2 :=1

  • 그렇지 않으면 cnt1과 cnt2를 1만큼 줄입니다.

• cnt1 :=0 및 cnt2 :=0

  설정

• 0 ~ n – 1 범위의 i에 대해

  • nums[i] =첫 번째이면 cnt1을 1 증가, 그렇지 않으면 nums[i]가 두 번째이면 cnt2를 1 증가

• ret

  라는 배열을 만듭니다.

• cnt1> n / 3이면 ret에 먼저 삽입

• cnt2> n / 3이면 두 번째를 ret에 삽입

• 반환 반환.

예시(C++)

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   vector<int> majorityElement(vector<int>& nums) {
      int first = 0;
      int second = 1;
      int cnt1 = 0;
      int cnt2 = 0;
      int n = nums.size();
      for(int i = 0; i < n; i++){
         int x = nums[i];
         if(x == first){
            cnt1++;
         }
         else if(x == second){
            cnt2++;
         }
         else if(cnt1 == 0){
            first = x;
            cnt1 = 1;
         }
         else if(cnt2 == 0){
            second = x;
            cnt2 = 1;
         } else {
            cnt1--;
            cnt2--;
         }
      }
      cnt1 = 0;
      cnt2 = 0;
      for(int i = 0; i < n; i++){
         if(nums[i] == first)cnt1++;
         else if(nums[i] == second)cnt2++;
      }
      vector <int> ret;
      if(cnt1 > n / 3)ret.push_back(first);
      if(cnt2 > n / 3)ret.push_back(second);
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {1, 1, 1, 3, 3, 2, 2, 2};
   print_vector(ob.majorityElement(v));
}

입력

[1,1,1,3,3,2,2,2]

출력

[2, 1, ]