分割数组为连续子序列

标签: 贪心 数组 哈希表 堆（优先队列）

难度: Medium

给你一个按 非递减顺序 排列的整数数组 nums 。

请你判断是否能在将 nums 分割成 一个或多个子序列 的同时满足下述 两个 条件：

  • 每个子序列都是一个 连续递增序列（即，每个整数 恰好 比前一个整数大 1 ）。
  • 所有子序列的长度 至少 为 3 。

如果可以分割 nums 并满足上述条件，则返回 true ；否则，返回 false 。

示例 1：

输入：nums = [1,2,3,3,4,5]
输出：true
解释：nums 可以分割成以下子序列：
[1,2,3,3,4,5] --> 1, 2, 3
[1,2,3,3,4,5] --> 3, 4, 5

示例 2：

输入：nums = [1,2,3,3,4,4,5,5]
输出：true
解释：nums 可以分割成以下子序列：
[1,2,3,3,4,4,5,5] --> 1, 2, 3, 4, 5
[1,2,3,3,4,4,5,5] --> 3, 4, 5

示例 3：

输入：nums = [1,2,3,4,4,5]
输出：false
解释：无法将 nums 分割成长度至少为 3 的连续递增子序列。

提示：

  • 1 <= nums.length <= 104
  • -1000 <= nums[i] <= 1000
  • nums 按非递减顺序排列

Submission

运行时间: 75 ms

内存: 16.8 MB

from collections import defaultdict

class Solution:
    def isPossible(self, nums: List[int]) -> bool:
        if len(nums) < 3:
            return False
        
        count = defaultdict(int)
        for n in nums:
            count[n] += 1

        tail = defaultdict(int)
        for n in nums:
            if count[n] == 0:
                continue
            if tail[n - 1] > 0:
                count[n] -= 1
                tail[n - 1] -= 1
                tail[n] += 1
                continue

            if count[n + 1] > 0 and count[n + 2] > 0:
                count[n] -= 1
                count[n + 1] -= 1
                count[n + 2] -= 1
                tail[n + 2] += 1
                continue

            return False

        return True

Explain

这个题解使用贪心算法和哈希表来判断能否将数组分割成满足条件的子序列。主要思路如下： 1. 先用一个哈希表count统计每个数字出现的次数 2. 再用一个哈希表tail记录以每个数字结尾的子序列个数 3. 遍历数组，对于每个数字n： - 如果n-1结尾的子序列个数大于0，则将n加入n-1结尾的子序列中 - 否则，如果n+1和n+2的计数都大于0，则将n, n+1, n+2作为新的子序列 - 如果上述两种情况都不满足，说明无法构成满足条件的分割，返回false 4. 遍历结束后，说明可以进行满足条件的分割，返回true

时间复杂度: O(n)

空间复杂度: O(n)

from collections import defaultdict

class Solution:
    def isPossible(self, nums: List[int]) -> bool:
        if len(nums) < 3:
            return False
        
        # 用哈希表count统计每个数字出现的次数
        count = defaultdict(int) 
        for n in nums:
            count[n] += 1

        # 用哈希表tail记录以每个数字结尾的子序列个数
        tail = defaultdict(int)
        for n in nums:
            if count[n] == 0: # 如果当前数字计数已为0，跳过
                continue
            if tail[n - 1] > 0: # 如果有以n-1结尾的子序列，将n加入该子序列 
                count[n] -= 1
                tail[n - 1] -= 1
                tail[n] += 1
                continue

            # 如果n+1和n+2的计数大于0，则将n,n+1,n+2作为新子序列
            if count[n + 1] > 0 and count[n + 2] > 0:
                count[n] -= 1
                count[n + 1] -= 1 
                count[n + 2] -= 1
                tail[n + 2] += 1
                continue

            # 无法生成满足条件的子序列，返回false
            return False

        # 可以生成满足条件的子序列，返回true
        return True

Explore

在算法执行过程中，当我们考虑将数字n加入到以n-1结尾的子序列时，我们不需要检查该子序列的长度是否至少为3，因为只要存在以n-1结尾的子序列，它的形成肯定已经符合了题目要求的最小长度3（或已经在此基础上扩展）。这是因为任何有效子序列在加入新元素之前，必须已经是一个有效的子序列。因此，我们只需关注是否存在以n-1结尾的子序列，而不需检查其具体长度。

在创建新的子序列时，选择n, n+1, n+2这三个连续数字是因为这样可以确保子序列的连续性且满足题目要求的最小长度3。如果选择了比n+2更大的数字，那么子序列中间会存在间断，不符合连续子序列的要求。如果选择长度小于3的子序列或不连续的数字，都将无法满足题目对连续子序列的定义。因此，n, n+1, n+2是构建符合题目要求的最基本、最简单的连续子序列的方式。

如果在处理某个数字n时，n+1或n+2的count为0，即这两个数字不能立即用来形成新的子序列，那么我们不能以n开始一个新的子序列。算法应继续向后查找，直到找到一个可以形成新子序列的位置，即找到一个新的n，其中n, n+1, n+2的count都大于0。这种延迟决策的方法有助于避免提前消耗数字，从而更灵活地应对后面的数字，保证了算法的贪心策略能够尽可能多地形成有效的子序列。

在算法执行过程中，如果某个数字n无法被加入到任何现有的子序列，并且也无法与其后的数字n+1和n+2一起形成一个新的子序列，那么算法将返回false。这种情况通常发生在以下几种情况：1) 当前数字n的后续数字n+1或n+2不存在或者它们的计数已经为0，使得无法形成新的连续子序列；2) 当前数字n也不能加入任何以n-1结尾的子序列，因为不存在这样的子序列。这两种情况表明，无法继续形成或扩展子序列，从而无法满足题目的要求。