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

[renmu123]

题目

给你一个整数数组 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

[Girlphobia]

有连续的 k 个整数 (a_0, ..., a_(k-1)) ，将每个数对 k 取模，余数必然遍历 0 到(k-1)。比如 [3,4,5,6,7] ，对 5 取模得到 [3,4,0,1,2] 。
那假设一共有 kn 个连续的 k 个整数，每个数列的所有数对 k 取模都有 0 到(k-1)每个数出现正好一次（在 loopkup 里面设置自增），那么在 lookup 里所有的 0 到(k-1)都应该出现 kn 次。
但是这个解法是有漏洞的，如果有 nums=[1,2,3,4,8,6] ，参考解法返回 True 而实际应为 False。

[Girlphobia]

@Girlphobia 更正：
nums=[1,2,3,4,8,6], k=3

[renmu123]

@Girlphobia 明白了，感谢大佬

[kiwi95]

应该把商也记一遍可以解决 1 楼说的问题

[Girlphobia]

@kiwi95 是的，两个字典可解

[gbin]

一种 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.

[gbin]

回复不支持 Markdown， 所以排版乱了，可以参考这里 https://0x400.com/2019-12-30-lc-1296-divide-array-in-sets-of-k-consecutive-numbers.html