Medium

题目描述

给你一个整数数组 nums 和一个正整数 k，请判断是否可以把这个数组分成一些由 k 个连续数字组成的集合。

如果可以，返回 true；否则，返回 false。

示例 1：

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

示例 2：

输入：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]。

示例 3：

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

提示：

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

注意： 这道题与第 846 题相同。

解题思路

解题思路

这道题要求将数组分成若干个由 k 个连续数字组成的集合。核心思路是贪心算法：

基本思路

  1. 频率统计：使用哈希表统计每个数字的出现次数
  2. 贪心策略：从最小的数字开始，尝试构建连续序列
  3. 验证条件：如果数组长度不是 k 的倍数，直接返回 false

具体步骤

  1. 首先检查数组长度是否能被 k 整除，如果不能则无法分组
  2. 统计每个数字的频率，存储在哈希表中
  3. 对所有不同的数字进行排序
  4. 从最小的数字开始，贪心地构建连续序列：
    • 如果当前数字的频次为 0，跳过
    • 否则，检查从当前数字开始的连续 k 个数字是否都存在且频次足够
    • 将这 k 个数字的频次都减 1
  5. 最后检查所有数字的频次是否都变为 0

时间优化

使用排序后的数字序列可以确保我们总是从最小的可用数字开始构建序列，这样可以避免后续无法形成完整序列的情况。

这种贪心策略是正确的，因为如果存在解，那么最小的数字必须作为某个序列的起始数字。

代码实现

class Solution {
public:
    bool isPossibleDivide(vector<int>& nums, int k) {
        if (nums.size() % k != 0) return false;
        
        map<int, int> count;
        for (int num : nums) {
            count[num]++;
        }
        
        while (!count.empty()) {
            int start = count.begin()->first;
            for (int i = 0; i < k; i++) {
                if (count[start + i] == 0) return false;
                count[start + i]--;
                if (count[start + i] == 0) {
                    count.erase(start + i);
                }
            }
        }
        
        return true;
    }
};

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        if len(nums) % k != 0:
            return False
        
        count = {}
        for num in nums:
            count[num] = count.get(num, 0) + 1
        
        sorted_nums = sorted(count.keys())
        
        for num in sorted_nums:
            if count[num] > 0:
                freq = count[num]
                for i in range(k):
                    if count.get(num + i, 0) < freq:
                        return False
                    count[num + i] -= freq
        
        return True

public class Solution {
    public bool IsPossibleDivide(int[] nums, int k) {
        if (nums.Length % k != 0) return false;
        
        var count = new SortedDictionary<int, int>();
        foreach (int num in nums) {
            count[num] = count.GetValueOrDefault(num, 0) + 1;
        }
        
        while (count.Count > 0) {
            int start = count.Keys.First();
            for (int i = 0; i < k; i++) {
                if (!count.ContainsKey(start + i) || count[start + i] == 0) {
                    return false;
                }
                count[start + i]--;
                if (count[start + i] == 0) {
                    count.Remove(start + i);
                }
            }
        }
        
        return true;
    }
}

var isPossibleDivide = function(nums, k) {
    if (nums.length % k !== 0) return false;
    
    const count = new Map();
    for (const num of nums) {
        count.set(num, (count.get(num) || 0) + 1);
    }
    
    const sortedNums = Array.from(count.keys()).sort((a, b) => a - b);
    
    for (const num of sortedNums) {
        if (count.get(num) > 0) {
            const freq = count.get(num);
            for (let i = 0; i < k; i++) {
                const current = num + i;
                if ((count.get(current) || 0) < freq) {
                    return false;
                }
                count.set(current, count.get(current) - freq);
            }
        }
    }
    
    return true;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)需要对数字进行排序，其中 n 是数组长度
空间复杂度O(n)哈希表存储数字频次，最坏情况下所有数字都不同

相关题目