V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
renmu123
V2EX  ›  LeetCode

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

  •  
  •   renmu123 · 2019-12-29 19:41:54 +08:00 · 10415 次点击
    这是一个创建于 1552 天前的主题,其中的信息可能已经有所发展或是发生改变。

    题目

    给你一个整数数组 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
    
    7 条回复    2019-12-30 22:16:14 +08:00
    Girlphobia
        1
    Girlphobia  
       2019-12-29 20:01:22 +08:00 via Android   ❤️ 1
    有连续的 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
        2
    Girlphobia  
       2019-12-29 20:02:37 +08:00 via Android
    @Girlphobia 更正:
    nums=[1,2,3,4,8,6], k=3
    renmu123
        3
    renmu123  
    OP
       2019-12-29 20:35:08 +08:00
    @Girlphobia 明白了,感谢大佬
    kiwi95
        4
    kiwi95  
       2019-12-29 20:43:07 +08:00 via iPhone
    应该把商也记一遍可以解决 1 楼说的问题
    Girlphobia
        5
    Girlphobia  
       2019-12-29 20:49:24 +08:00 via Android
    @kiwi95 是的,两个字典可解
    gbin
        6
    gbin  
       2019-12-30 21:52:48 +08:00
    一种 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
        7
    gbin  
       2019-12-30 22:16:14 +08:00
    回复不支持 Markdown, 所以排版乱了,可以参考这里 https://0x400.com/2019-12-30-lc-1296-divide-array-in-sets-of-k-consecutive-numbers.html
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2786 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 12:29 · PVG 20:29 · LAX 05:29 · JFK 08:29
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.