C++のマジョリティエレメントII

したがって、入力が[1,1,1,3,3,2,2,2]の場合、結果は[1,2]

これを解決するには、次の手順に従います-

• 最初の：=0、2番目の：=1、cnt1：=0、cnt2：=0、n：=配列番号のサイズ

• 0からn–1のサイズのiの場合

  • x：=nums [i]

  • xが最初の場合、cntを1増やします

  • それ以外の場合、xが2番目の場合は、cnt2を1増やします

  • それ以外の場合、cnt1が0の場合、最初にxおよびcnt1：=1

    として設定します。

  • それ以外の場合、cnt2が0の場合、2番目をxおよびcnt2：=1

    として設定します。

  • それ以外の場合は、cnt1とcnt2を1減らします

• cnt1：=0およびcnt2：=0

  を設定します

• 0からn–1の範囲のiの場合

  • nums [i] =が最初の場合、cnt1を1増やします。それ以外の場合、nums [i]が2番目の場合、cnt2を1増やします

    。

• retと呼ばれる配列を作成します

• cnt1> n / 3の場合、最初にretに挿入します

• cnt2> n / 3の場合、2番目をretに挿入します

• 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, ]