C++で配列をK個の連続する整数のセットに分割できるか判定する方法

問題概要

整数型の配列 nums と正整数 k が与えられます。この配列を「連続する k 個の整数」からなるセットに完全に分割できるかどうかを判定し、可能であれば true を、不可能であれば false を返してください。

たとえば、入力が [1,2,3,3,4,4,5,6]、k = 4 の場合を考えてみましょう。この配列は [1,2,3,4] と [3,4,5,6] の2つのセットに分割できるため、答えは true(出力は 1)になります。

解法のアプローチ

この問題は、マップ(連想配列)で各数値の残り出現回数を管理しながら、昇順にグループを形成していくことで効率よく解けます。手順は以下の通りです。

1. マップ m を用意し、n を配列 nums のサイズとします。
2. nums の各要素 e について m[e] を1増やし、出現回数を記録します。
3. 消費済み要素数を数える変数 cnt を 0 で初期化します。
4. 配列 nums を昇順にソートします。
5. i が 0 から n-1 までの範囲で以下を繰り返します。
   • x := nums[i] とします。
   • m[x - 1] == 0 かつ m[x] > 0 の場合、x は新しいグループの先頭候補です。長さ k のグループ構築を試みます。
     • l := k として現在の k を退避します。
     • k > 0 の間、次を繰り返します。m[x] > 0 であれば m[x] を1減らします。該当する数が残っていなければ即座に false を返します。その後、x を1増やし、cnt を1増やし、k を1減らします。
     • グループ構築後、k := l として元の値に戻します。
6. 最後に、cnt == n であれば true を、そうでなければ false を返します。

ポイントは、ソート済みの配列を先頭から走査し、「直前の数(m[x-1])が残っていない」要素だけをグループの始点として扱うことです。これにより、すべての数が必ずどこかの連続シーケンスに割り当てられ、途中で必要な連続する数が不足すれば分割不可能と判断できます。

C++による実装例

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

入力例

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

出力例

1

計算量

ソートに O(n log n) かかり、その後の走査では各要素が定数回ずつ処理されるため、全体の時間計算量は O(n log n) です。マップの各操作も O(log n) であるため、合計でも O(n log n) に収まります。空間計算量はマップの分の O(n) です。