C++で解く「最大等頻度」問題：1要素削除後に頻度が揃う最長接頭辞の求め方

正の整数からなる配列 nums が与えられたとき、その配列の接頭辞（先頭からの連続する部分配列）の中で、「そこからちょうど1つの要素を削除した後に、出現するすべての数値の頻度が等しくなる」という条件を満たす、最も長い接頭辞の長さを返すことを考えます。なお、要素を1つ削除した結果として残りの要素が空になった場合でも、すべての数値の頻度が等しい（すべて0）とみなされます。

例えば、入力が [3,3,2,2,6,4,4,6] の場合、答えは 7 になります。インデックス4にある要素 6 を削除すると、接頭辞は [3,3,2,2,4,4] となり、すべての要素がちょうど2回ずつ出現するためです。

アルゴリズムの考え方

この問題は、配列を左から順に走査しながら、各時点での「値ごとの出現回数」と「出現回数ごとの値の種類数」を2つのマップで管理することで効率的に解けます。

具体的には、以下の手順に従います。

• maxf := 0（最大頻度）、res := 0(結果の長さ) と初期化する

• マップ cnt（各値の出現回数）と freq（各頻度を持つ値の種類数）を定義する

• i := 0 から開始し、i が nums のサイズ未満である間、i を1ずつ増やしながら以下を繰り返す：

  • x := nums[i]

  • cnt[x] を1増やす

  • f := cnt[x]

  • freq[f] を1増やし、freq[f - 1] を1減らす（頻度の移動を反映）

  • maxf := max(maxf, f)

  • 次のいずれかの条件を満たす場合、res := i + 1 と更新する：

    • maxf * freq[maxf] == i … すべての要素が同じ頻度 maxf で出現している状態

    • (maxf - 1) * (freq[maxf - 1] + 1) == i … 最頻値が1つだけ他より1回多く出現しており、その1つを削除すれば頻度が揃う状態

    • maxf == 1 … すべての要素が1回ずつしか出現していない状態（どれか1つを削除すればよい）

• 最後に res を返す

これらの条件により、各位置 i において「1要素の削除で頻度を均一にできるか」を O(1) で判定でき、全体の計算量は O(n log n)（マップの操作コスト込み）に抑えられます。

理解を深めるために、以下のC++による実装を見てみましょう。

実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int maxEqualFreq(vector<int>& nums) {
      int maxf = 0, res = 0;
      map<int, int> cnt, freq;
      for (int i = 0; i < nums.size(); i++) {
         int x = nums[i];
         cnt[x]++;
         int f = cnt[x];
         freq[f]++;
         freq[f - 1]--;
         maxf = max(maxf, f);
         if (maxf * freq[maxf] == i || (maxf - 1) * (freq[maxf - 1] + 1) == i || maxf == 1) {
            res = i + 1;
         }
      }
      return res;
   }
};
main(){
   Solution ob;
   vector<int> v = {3,3,2,2,6,4,4,6};
   cout << (ob.maxEqualFreq(v));
}

入力

{3,3,2,2,6,4,4,6}

出力

7