Leetcode 1296:划分数组为连续数字的集合(超详细的解法!!!)
给你一个整数数组 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
解题思路
首先我们可以排除一个边界条件,就是当len(nums)%k != 0
的时候,肯定是返回False
。
这个问题有一个很容易想到的思路,首先我们将所有的数字统计一遍(使用字典存储),然后以key
最小值作为左边界l
,寻找大小为k
的区间是不是存在,如果不存在返回False
(也就是判断l
后面的数对应字典的值是不是比l
对应的字典值小,如果比之小,那么我们就知道后面的数不够和其构成集合;如果比之大的话,我们知道满足条件,所以将其排除,也就是减去l
对应的字典值的大小)。
这个问题的难点在于代码的实现,代码的实现有很多细节需要考虑。首先统计元素出现次数,可以使用hashmap
也可以使用treemap
,如果是前者的话,我们还需对keys
进行排序,因为需要获取最小的key
;而使用后者的话,因为treemap
有序,所以无需上述操作。(在python
中,dict
、collections.Counter
等对应的就是hashmap
,所以我们需要对keys
进行一次排序)
class Solution:
def isPossibleDivide(self, nums: List[int], k: int) -> bool:
if len(nums) % k != 0:
return False
cnt = collections.Counter(nums)
keys = sorted(cnt)
for n in keys:
t = cnt[n]
if t:
for i in range(n, n + k):
if cnt[i] < t:
return False
cnt[i] -= t
return True
上面的代码还有一个变形,就是对于后面的元素减去左边界结果为0
的数,我们将其删除。
class Solution:
def isPossibleDivide(self, nums: List[int], k: int) -> bool:
if len(nums) % k != 0:
return False
cnt = collections.Counter(nums)
while len(cnt):
l = min(cnt)
t, new_l = cnt[l], -1
for i in range(l, l + k):
if cnt[i] < t:
return False
else:
cnt[i] -= t
if cnt[i] == 0:
cnt.pop(i)
return True
这种做法貌似效率比不删除元素的效率高,但也只是针对特定的语言环境。如果使用的是treemap
的话,删除元素的效率就是O(logn)
,所以很可能删除元素的时间本身就很高。而使用hashmap
的效率是O(1)
啊,那是不是一定就很好呢?也不一定,例如在java
中想要删除一个map
中的节点,就必须使用迭代器,那么就需要遍历元素去查找待删除节点,这种时间复杂度就是O(n)
,反而更慢了。那就是变慢了吗?也不一定,我们注意到当我们使用hashmap
的时候,使用了排序获取有序的keys
,也就是O(nlogn)
的效率。
如果我们直接使用min
方法呢?当不删除元素的时候,直接使用min
的效率就是O(n^2)
;但是当删除元素的时候,那么min
判断的次数就会减小。在实际测试中cpp
使用min and erase
的策略表现不错,而在java
中使用sort and not erase
的方式最佳。
我将该问题的其他语言版本添加到了我的GitHub Leetcode
如有问题,希望大家指出!!!