C++で解く Majority Element II ― n/3回より多く出現する要素をO(n)で見つける方法

問題概要

整数型の配列が与えられたとき、その中から「n/3 の切り捨て値（⌊n/3⌋）よりも多く出現する要素」をすべて見つけることを考えます。ここで n は配列のサイズです。

例えば、入力が [1,1,1,3,3,2,2,2] の場合を考えてみましょう。1 は 3 回、2 は 3 回出現しており、どちらも ⌊8/3⌋ = 2 より大きいため、答えは [1, 2] となります。

ここで重要な性質として、「n/3 を超える回数出現する要素は最大でも 2 種類しか存在しない」ことが挙げられます。もし 3 つの異なる要素がそれぞれ n/3 回より多く現れると、合計出現回数が n を超えてしまい矛盾するためです。この性質が、次に紹介するアルゴリズムの鍵となります。

アルゴリズム：Boyer-Moore 投票法の拡張

この問題は、マジョリティ要素（n/2 超の出現）を求める際に使われる Boyer-Moore 投票法を、候補を 2 つに拡張することで効率的に解けます。手順は以下の通りです。

• first := 0、second := 1、cnt1 := 0、cnt2 := 0 と初期化し、n を配列 nums のサイズとします。
• i を 0 から n−1 まで順に処理します。
  • x := nums[i] とします。
  • x が first と等しければ cnt1 を 1 増やします。
  • そうでなく x が second と等しければ cnt2 を 1 増やします。
  • そうでなく cnt1 が 0 ならば、first := x、cnt1 := 1 とします。
  • そうでなく cnt2 が 0 ならば、second := x、cnt2 := 1 とします。
  • いずれの条件にも当てはまらなければ、cnt1 と cnt2 をそれぞれ 1 減らします。
• cnt1 := 0、cnt2 := 0 にリセットします。
• 再び i を 0 から n−1 まで走査し、nums[i] が first なら cnt1 を、second なら cnt2 を増やして実際の出現回数を数えます。
• 結果格納用の配列 ret を用意します。
• cnt1 > n/3 であれば first を ret に挿入します。
• cnt2 > n/3 であれば second を ret に挿入します。
• ret を返します。

最初の走査で候補を 2 つに絞り込み、2 回目の走査で検証を行うという 2 段階構成がポイントです。これにより、計算量は時間 O(n)、追加メモリ O(1) に抑えられます。

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]

このように、n/3 を超える出現回数を持つ 2 つの要素（1 と 2）が正しく検出されています。候補の初期値や走査の順序によって出力される順番は変わることがありますが、結果として得られる要素の集合は正しいものです。