C++で配列を連続する整数の部分列に分割できるか判定するアルゴリズム

問題の概要

昇順にソートされた整数型配列 nums が与えられます。この配列を1つ以上のサブシーケンス(部分列)に分割できる場合にのみ true を返してください。ただし、各サブシーケンスは次の条件を満たす必要があります。

• 連続する整数で構成されていること
• 長さが3以上であること

例えば、入力が [1,2,3,3,4,4,5,5] の場合、出力は true になります。[1,2,3,4,5] と [3,4,5] という2つの連続した数列に分割できるためです。

解決アプローチ

この問題は、ハッシュマップで各要素の出現頻度を管理しながら、貪欲法(グリーディ法)で処理を進めることで効率的に解けます。考え方として、小さい値から順に「x, x+1, x+2」の組を作って長さ3を確保し、その後さらに後続の要素で数列を伸ばせるかどうかを判定していきます。

アルゴリズムの手順

1. マップ m を作成し、nums 内の各要素の出現回数を記録します。また、配列のサイズを n として保存します。
2. 未処理の要素数を表す変数 cnt を n で初期化します。
3. i を 0 から n-1 までループさせます。
   • x = nums[i] とします。
   • m[x]、m[x+1]、m[x+2] がすべて残っている場合:
     • m[x]、m[x+1]、m[x+2] をそれぞれ1減らし、x に3を加算、cnt から3を引きます。
     • m[x] > 0 かつ m[x] > m[x-1] が成り立つ間、次の処理を繰り返します。
       • cnt を1減らし、m[x] を1減らし、x を1増やします。(現在の連続数列をさらに延長)
4. すべての処理が終わった後、cnt が 0 であれば true、そうでなければ false を返します。

この貪欲な割り当てにより、余分な重複要素が必ずどこかの長さ3以上の連続数列に所属することになり、全体を適切に分割できるかを正しく判定できます。

C++での実装例

以下のコードで実際の動作を確認できます。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    bool isPossible(vector<int>& nums) {
        unordered_map<int, int> m;
        int n = nums.size();
        for(int i = 0; i < n; i++){
            m[nums[i]]++;
        }
        int cnt = n;
        for(int i = 0; i < n; i++){
            int x = nums[i];
            if(m[x] && m[x + 1] && m[x + 2]){
                m[x]--;
                m[x + 1]--;
                m[x + 2]--;
                x += 3;
                cnt -= 3;
                while(m[x] > 0 && m[x] > m[x - 1]){
                    cnt--;
                    m[x]--;
                    x++;
                }
            }
        }
        return cnt == 0;
    }
};
main(){
    vector<int> v = {1,2,3,3,4,4,5,5};
    Solution ob;
    cout << (ob.isPossible(v));
}

入力例

[1,2,3,3,4,4,5,5]

出力例

1

計算量について

各要素はマップへの登録と貪欲な割り当てでそれぞれ定数回ずつ処理されるため、時間計算量は unordered_map 使用時で平均 O(n)、空間計算量は O(n) となります。大規模な入力に対しても高速に動作するのが特徴です。