欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Leetcode 1296:划分数组为连续数字的集合(超详细的解法!!!)

程序员文章站 2022-07-12 08:46:39
...

给你一个整数数组 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中,dictcollections.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

如有问题,希望大家指出!!!