题目

给你一个整数数组 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 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
1 <= k <= nums.length

来源：力扣（ LeetCode ）链接： https://leetcode-cn.com/problems/divide-array-in-sets-of-k-consecutive-numbers 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的解答过程和众评论里的相似，但是看到一个速度排行榜前面大佬的代码我就搞不明白原理了，萌新求指教

大佬的解答过程

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        n = len(nums)
        if n % k != 0:
            return False
        for i in range(len(nums)):
            nums[i] %= k
        lookup = {}
        for val in nums:
            if val in lookup:
                lookup[val] += 1
            else:
                lookup[val] = 1
        kn = n // k
        for i in range(k):
            if lookup[i] != kn:
                return False
        return True

gbin

2019-12-30 21:52:48 +08:00

一种 nlogn 的解法
统计每个数字出现的次数放在一个 map 中，然后从最小元素开始暴力循环，只要 map 不为空，求得当前最小值 cur, 从 cur 开始，对于任意 0 到 k 满足：
1. cur 存在 map 中 (cur in map)
2. map[cur] 减 1 后，如果 map[cur] 已经为 0 则删除 cur 这个 key
3. cur += 1

若所有组合都满足以上条件则说明可以被划分成多份 k 个连续的子数组，否则不可以。

代码如下：

```
class Solution:
def isPossibleDivide(self, nums: List[int], k: int) -> bool:
map = collections.Counter(nums)
while map:
cur = min(map.keys())
for _ in range(k):
if cur not in map:
return False
else:
map[cur] -= 1
if map[cur] == 0:
del map[cur]
cur += 1
return True
```

提交后一遍通过，但是效率有点低，供你讨论 :)
Runtime: 500 ms, faster than 33.77% of Python3 online submissions for Divide Array in Sets of K Consecutive Numbers.
Memory Usage: 27.2 MB, less than 100.00% of Python3 online submissions for Divide Array in Sets of K Consecutive Numbers.

leetcode 刷题遇到的疑惑 1296. 划分数组为连续数字的集合

题目

大佬的解答过程