C++で配列の次数を求める方法｜最短部分配列の長さを計算するアルゴリズム解説

問題の概要

負でない整数からなる配列 nums があるとします。この配列の「次数（degree）」とは、配列内のいずれか一つの要素が出現する最大頻度のことです。ここでの課題は、nums と同じ次数を持つ連続した部分配列のうち、可能な限り短い長さを見つけることです。

例えば、入力が [1, 2, 2, 3, 1] の場合、出力は 2 になります。これは、入力配列において要素 1 と 2 がそれぞれ2回出現しているため、配列の次数は 2 となるからです。同じ次数 2 を持つ部分配列には、次のようなものがあります。

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

この中で最も短いのは長さ 2 の [2, 2] であるため、答えは 2 となります。

解法のアプローチ

この問題は、頻度カウント用の配列とスライディングウィンドウ（尺取り法）を組み合わせることで効率的に解くことができます。手順は以下の通りです。

1. サイズ 50000 の配列 freq を定義し、すべて 0 で初期化します。
2. 変数 max_ を 0 で初期化します。
3. nums の各要素 n に対して、freq[n] を 1 増やし、max_ を max_ と freq[n] の最大値に更新します。これで配列全体の次数が求まります。
4. freq 配列を再度すべて 0 で埋めてリセットします。
5. 変数 min_ を nums のサイズで初期化します。
6. スライディングウィンドウを使ってループ処理を行います。
   • j >= 0 かつ freq[nums[j]] が max_ と等しい場合：min_ を min_ と j - i + 1 の最小値に更新し、左端の要素をウィンドウから取り除きます。
   • そうでなく j < size - 1 の場合：j を 1 増やして右端を拡張し、freq[nums[j]] を 1 増やします。
   • それ以外の場合はループを抜けます。
7. min_ を返します。

C++での実装例

それでは、理解を深めるために実際の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int findShortestSubArray(vector<int>& nums) {
        vector<int> freq(50000, 0);
        int max_ = 0;
        for (const int n : nums)
            max_ = max(max_, ++freq[n]);
        fill(freq.begin(), freq.end(), 0);
        int min_ = nums.size();
        for (int i = 0, j = -1, size = nums.size(); j < size;) {
            if (j >= 0 && freq[nums[j]] == max_)
                min_ = min(min_, j - i + 1), --freq[nums[i++]];
            else if (j < size - 1)
                ++freq[nums[++j]];
            else
                break;
        }
        return min_;
    }
};
main(){
    Solution ob;
    vector<int> v = {1, 2, 2, 3, 1};
    cout << (ob.findShortestSubArray(v));
}

入力

{1, 2, 2, 3, 1}

出力

2

計算量の分析

このアルゴリズムの計算量は以下の通りです。

• 時間計算量：O(n)。配列を最大2回走査するだけで済むため、線形時間で処理できます。
• 空間計算量：O(1)。freq 配列は要素の値域に応じた固定サイズであり、入力サイズ n に比例して増加しないため、追加メモリは定数とみなせます。

まとめ

配列の次数を求める問題は、まず各要素の出現回数をカウントして最大頻度を特定し、その後スライディングウィンドウで同じ次数を持つ最短の連続部分配列を探索することで解決できます。LeetCode の「Degree of an Array」問題としても知られる定番のアルゴリズム課題ですので、頻度カウントと尺取り法を組み合わせるテクニックとしてぜひ習得しておきましょう。