划分数组为连续数字的集合

标签: 贪心 数组 哈希表 排序

难度: 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 = [3,3,2,2,1,1], k = 3
输出：true

示例 4：

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

提示：

  • 1 <= k <= nums.length <= 105
  • 1 <= nums[i] <= 109

注意：此题目与 846 重复：https://leetcode-cn.com/problems/hand-of-straights/

Submission

运行时间: 107 ms

内存: 31.7 MB

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        nums_count = {}
        for num in nums:
            if num in nums_count:
                nums_count[num]+=1
            else:
                nums_count[num] = 1

        for key in sorted(nums_count.keys()):
            value = nums_count[key]
            if value==0:
                continue
            for i in range(k):
                if i+key not in nums_count:
                    return False
                nums_count[i+key]-=value
                if nums_count[i+key]<0:
                    return False
        return True

Explain

此题解采用的方法是首先统计数组中每个数字出现的次数，存储在一个哈希表中。然后，对哈希表的键（即数字）进行排序，以保证从最小的数字开始处理。对每个数字，如果它还未完全用于构成之前的连续子集，会尝试构造以该数字为起点，长度为 k 的连续数字子集。每次尝试减去相应数量，如果在此过程中发现某个数字不足以形成连续子集，直接返回 False。如果能成功构造出所有连续子集，则返回 True。

时间复杂度: O(n + u log u + nk)

空间复杂度: O(n)

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        # 创建哈希表存储每个数字的出现次数
        nums_count = {}
        for num in nums:
            if num in nums_count:
                nums_count[num]+=1
            else:
                nums_count[num] = 1

        # 遍历已排序的键
        for key in sorted(nums_count.keys()):
            value = nums_count[key]
            if value==0:
                continue
            # 尝试构造连续的k个数字组成的序列
            for i in range(k):
                if i+key not in nums_count:
                    return False
                nums_count[i+key]-=value
                if nums_count[i+key]<0:
                    return False
        return True

Explore

在处理哈希表键时需要先进行排序以确保从最小的数字开始尝试构建连续的数字序列。这是因为算法的目标是构造连续的数字集合，如果键没有排序，就可能首先遇到较大的数字，这会使得在尝试构建连续集合时出现逻辑上的错误和复杂性。排序后，我们可以系统地从最小的数字开始，一步步向上检查并构建连续序列，确保每个数字都能在其可能的最小序列中被使用。

即使`nums_count[i+key]`的值已经为0，我们仍然需要继续检查后续的数字，因为算法需要验证从当前数字开始的连续k个数字是否都可用于构成一个子集。一个数字的计数为0表示它已被完全使用在其他子集中，如果后续数字不能满足构造连续子集的需求，这意味着整体构造过程失败，因此需要返回False。这个检查确保了所有需要的数字都是按顺序可用的。

在算法中，如果在尝试构建连续子集时减去的`value`大于`nums_count[i+key]`中记录的实际数量，那么`nums_count[i+key]`将会变成负数。这种情况表明无法从`i+key`开始构建足够长的连续子集，因为所需的数字数量不足。这时算法会检测到`nums_count[i+key]<0`的情况，并立即返回False，表示不能成功地将数组划分成所需的连续数字集合。

算法在遇到无法构成序列的情况时直接返回False的实现方式已经考虑了所有关键的边界条件，尤其是涉及数字可用性的检查。每次尝试构造连续子集之前，都会检查当前数字及其后续k-1个数字的可用性。如果任何一个数字不足以支持连续子集的构建，算法将返回False。这保证了只要有任何一组连续数字不能被完全匹配，整个函数都会正确地返回False，避免了错误地认为可以分割数组。