题目描述

给你一个整数数组 nums 和一个正整数 k，请你判断是否可以把这个数组划分成一些由 k 个连续数字组成的集合。
如果可以，请返回 True；否则，返回 False。

样例

输入：nums = [1,2,3,3,4,4,5,6], k = 4
输出：true
解释：数组可以分成 [1,2,3,4] 和 [3,4,5,6]。

输入：nums = [3,2,1,2,3,4,3,4,5,9,10,11], k = 3
输出：true
解释：数组可以分成 [1,2,3] , [2,3,4] , [3,4,5] 和 [9,10,11]。

输入：nums = [3,3,2,2,1,1], k = 3
输出：true

输入：nums = [1,2,3,4], k = 3
输出：false
解释：数组不能分成几个大小为 3 的子数组。

限制

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9
• 1 <= k <= nums.length

算法1

(多重集，暴力枚举) $O(n \log n)$

1. 用 C++ 的多重集 multiset 来维护整个数组。
2. 对于每一组，第一个数字肯定是当前多重集的最小值，然后依次从多重集中判断是否存在连续的 k 个数字，并从多重集中删除。

时间复杂度

• 多重集的查找和删除的时间复杂度为 $O(\log n)$，最多有 $n$ 次这样的操作，故总时间复杂度为 $O(n \log n)$。

空间复杂度

• 需要额外 $O(n)$ 的空间存储多重集。

C++ 代码

class Solution {
public:
    bool isPossibleDivide(vector<int>& nums, int k) {
        int n = nums.size();
        if (n % k)
            return false;

        multiset<int> s(nums.begin(), nums.end());

        for (int i = 0; i < n / k; i++) {
            int x = *s.begin();
            for (int j = 0; j < k; j++)
                if (s.find(x) != s.end()) {
                    s.erase(s.find(x));
                    x++;
                } else {
                    return false;
                }
        }
        return true;
    }
};

算法2

(排序，哈希表) $O(n \log n)$

1. 将数组排序，并统计出每个数字的出现次数。
2. 按顺序扫每个数字，如果当前数字的出现次数大于 0，则这个数字 x 必须作为连续的 k 个数字的开头，在哈希表中将 [x, x + k - 1] 减 1。
3. 更新哈希表的过程中，如果其中某个数字出现次数为 0，则宣布失败。

时间复杂度

• 排序的时间复杂度为 $O(n \log n)$，哈希表操作的时间复杂度均为常数，一共操作 $O(n)$ 次哈希表。
• 故总时间复杂度为 $O(n \log n)$。

空间复杂度

• 需要额外 $O(n)$ 的空间存放哈希表。

C++ 代码

class Solution {
public:
    bool isPossibleDivide(vector<int>& nums, int k) {
        int n = nums.size();
        if (n % k)
            return false;

        sort(nums.begin(), nums.end());

        unordered_map<int, int> counter;
        for (int x : nums)
            counter[x]++;

        for (int x : nums)
            if (counter[x] > 0)
                for (int j = x; j < x + k; j++) {
                    if (counter[j] == 0)
                        return false;
                    counter[j]--;
                }

        return true;
    }
};