C++で配列のサイズを半分に削減するアルゴリズム

問題概要

配列 arr が与えられているとします。私たちはいくつかの整数からなる集合を選び、その集合に含まれるすべての整数を配列から取り除くことができます。ここで求めたいのは、配列の要素の少なくとも半分が取り除かれるようにするために必要な「集合の最小サイズ」です。

例として、arr = [3,3,3,3,5,5,5,2,2,7] の場合を考えてみましょう。このとき出力は 2 になります。{3,7} を選択すると、新しい配列は [5,5,5,2,2] となり、そのサイズが5（元の配列サイズ10のちょうど半分）になるためです。

サイズ2の候補としては {3,5}、{3,2}、{5,2} などがあります。一方で {2,7} を選ぶことはできません。この場合、新しい配列は [3,3,3,3,5,5,5] となり、サイズが7と元の配列の半分よりも大きくなってしまうからです。

解決のためのアプローチ

この問題は、次の手順に従うことで解決できます。

• マップ m を定義し、n に配列のサイズを代入します。さらに、配列内の各要素の出現回数（頻度）をマップ m に記録します。

• 一時的な配列 temp を定義し、sz を n に、結果用の変数 ret を0に初期化します。

• マップ m 内の各キー・バリューのペア it について、その値（＝出現回数）を temp に追加します。

• temp 配列を降順にソートします。

• i を 0 から temp のサイズまでループさせます。

  • もし sz <= n / 2 であれば、ループを抜けます。

  • ret を1増やします。

  • sz から temp[i] を引きます。

• 最後に ret を返します。

この手法のポイントは貪欲法（グリーディ法）にあると言えます。出現回数の多い要素から順に除去していくことで、最小の集合サイズで半分以上の要素を削除できる可能性が高まります。

C++による実装例

理解を深めるために、次の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int minSetSize(vector<int>& arr) {
      unordered_map <int, int> m;
      int n = arr.size();
      for(int i = 0; i < n; i++){
         m[arr[i]]++;
      }
      vector <int> temp;
      unordered_map <int, int> :: iterator it = m.begin();
      int sz = n;
      int ret = 0;
      while(it != m.end()){
         temp.push_back(it->second);
         it++;
      }
      sort(temp.rbegin(), temp.rend());
      for(int i = 0; i < temp.size(); i++){
         if(sz <= n / 2)break;
         ret++;
         sz -= temp[i];
      }
      return ret;
   }
};
main(){
   vector<int> v = {3,3,3,3,5,5,5,2,2,7};
   Solution ob;
   cout << (ob.minSetSize(v));
}

入力

[3,3,3,3,5,5,5,2,2,7]

出力

2

まとめ

この問題では、各要素の出現頻度を数え上げ、頻度の高い要素から順に選んでいく貪欲な戦略が有効です。計算量は、ハッシュマップへの頻度記録に O(n)、ソートに O(k log k)（k はユニークな要素数）程度であり、多くの場合で効率的に動作します。頻度の高い要素ほど除去効果が大きいため、直感的にも理論的にも最短手順に近い結果が得られるのが特徴です。