1296. Divide Array in Sets of K Consecutive Numbers

描述

题目描述 - https://leetcode.com/problems/divide-array-in-sets-of-k-consecutive-numbers
给定一个数组 nums 和整数 k，判断是否将数组 nums 分成有 k 个连续数字组成的若干子数组。

Example 1:

1
2
3

Input: nums = [1,2,3,3,4,4,5,6], k = 4
Output: true
Explanation: Array can be divided into [1,2,3,4] and [3,4,5,6].

Example 2:

1
2
3

Input: nums = [1,2,3,4], k = 3
Output: false
Explanation: Each array should be divided in subarrays of size 3.

分析

统计每个数字出现的次数放在一个 map 中，然后从最小元素开始暴力循环，只要 map 不为空，求得 map 中当前最小值 cur, 从 cur 开始，对于任意 0 到 k 满足：

cur 存在 map 中 (cur in map)
map[cur] 减 1 后，如果 map[cur] 已经为 0 则删除 cur 这个 key
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
                map[cur] -= 1
                if map[cur] == 0:
                    del map[cur]
                cur += 1
        return True

提交后一遍通过。