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 满足:

  1. cur 存在 map 中 (cur in map)
  2. map[cur] 减 1 后,如果 map[cur] 已经为 0 则删除 cur 这个 key
  3. cur += 1

则说明可以被划分成多份 k 个连续的子数组,否则不可以。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
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

提交后一遍通过。

本文标题:1296. Divide Array in Sets of K Consecutive Numbers

文章作者:Pylon, Syncher

发布时间:2019年12月30日 - 19:12

最后更新:2023年03月11日 - 17:03

原始链接:https://0x400.com/fundamental/algorithm/lc-1296-divide-array-in-sets-of-k-consecutive-numbers/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。