659. 分割数组为连续子序列 #

问题描述#

给你一个按升序排序的整数数组 num（可能包含重复数字），请你将它们分割成一个或多个子序列，其中每个子序列都由连续整数组成且长度至少为 3 。

如果可以完成上述分割，则返回 true ；否则，返回 false 。

示例 1：
输入: [1,2,3,3,4,5]
输出: True
解释:
你可以分割出这样两个连续子序列 : 
1, 2, 3
3, 4, 5
示例 2：
输入: [1,2,3,3,4,4,5,5]
输出: True
解释:
你可以分割出这样两个连续子序列 : 
1, 2, 3, 4, 5
3, 4, 5
示例 3：
输入: [1,2,3,4,4,5]
输出: False
提示：

输入的数组长度范围为 [1, 10000]

解题思路#

对于一个数 \(x\)，

如果存在以 \(x-1\) 结尾的序列，如果这样的序列有多个，那么需要将 \(x\) 连接到其中最短的一个序列上（假设长度为 \(L\)），并且将这个最短的以 \(x-1\) 结尾的序列删去，因为这个最短序列已经变为以 \(x\) 结尾的长度为 \(L+1\) 的序列了。

如对于序列 \([1,2,3,3,4,5]\)，当遍历到 4 时，存在两个以 3 结尾的序列 \([1,2,3]\) 和 \([3]\)，这时应该将 4 连接到 \([3]\) 上，然后在以 3 结尾的序列中删去 \([3]\)，同时增加一个以 4 结尾的序列 \([3,4]\).
不存在以 \(x-1\) 结尾的序列，添加一个以 \(x\) 结尾的序列 \([x]\).

因为每次需要获取前一个数的最短序列长度，所以考虑使用优先队列。

import heapq
from collections import defaultdict
from typing import List

class Solution:
    def isPossible(self, nums: List[int]) -> bool:
        end = defaultdict(list)
        for x in nums:
            if end[x - 1]:  # 存在以 x-1 结尾的序列
                L = heapq.heappop(end[x - 1])  # 获取其中最短的长度并删去
                heapq.heappush(end[x], L + 1)  # 添加一个以 x 结尾的序列
            else:
                # 不存在以 x-1 结尾的序列
                # 添加一个以 x 结尾的长度为 1 的序列
                heapq.heappush(end[x], 1)
        for x in end:
            # 存在以 x 结尾的序列长度小于 3
            if end[x] and heapq.heappop(end[x]) < 3:
                return False
        return True

因为要求的是序列长度不小于 3，所以对于 \(x\) 来说，连接到以 \(x-1\) 结尾的长度大于等于 3 的序列都一样。

所以可以使用三个字典来分别保存以 \(x-1\) 结尾的长度为 1、长度为 2、长度大于等于 3 的序列数量。

from collections import defaultdict
from typing import List

class Solution:
    def isPossible(self, nums: List[int]) -> bool:
        L1, L2, L3 = defaultdict(int), defaultdict(int), defaultdict(int)
        for x in nums:
            if L1[x - 1]:  # 以 x-1 结尾的长度为 1 的序列数量
                L1[x - 1] -= 1
                L2[x] += 1
            elif L2[x - 1]:  # 以 x-1 结尾的长度为 2 的序列数量
                L2[x - 1] -= 1
                L3[x] += 1
            elif L3[x - 1]:  # 以 x-1 结尾的长度大于等于 3 的序列数量
                L3[x - 1] -= 1
                L3[x] += 1
            else:
                L1[x] += 1
        for x in L1:
            if L1[x]:  # 如果存在以 x 结尾的长度为 1 的序列
                return False
        for x in L2:
            if L2[x]:  # 如果存在以 x 结尾的长度为 2 的序列
                return False
        return True

遍历到 \(x\) 时，它能够组合成满足要求的序列的可能情况为：

连接到某个大于等于 3 的序列的末尾
组成 \([x-2,x-1,\boxed{x}]\)
组成 \([x-1,\boxed{x},x+1]\)
组成 \([\boxed{x},x+1,x+2]\)

对于情况 2，如果存在 \([x-2,x-1,x]\) 这样的序列，按照情况 4，它会被 \(x-2\) 首先使用掉。

同理对于情况 3，\([x-1,x,x+1]\) 会被 \(x-1\) 使用掉。

所以只存在 1 和 4 两种情况使得 \(x\) 能够组合成满足条件的子序列。

但是情况 3 和情况 4 不是等价的，也就是说，它们存在判断的先后顺序。

比如说对于序列 \([1,2,3,4,5,5,6,7]\)，按照先情况 1 然后情况 4 进行判断，它最后的组合结果为 \([1,2,3,4,5]\) 和 \([5,6,7]\)，能够分割。若按照先情况 4 然后情况 1 进行判断，它的组合结果为 \([1,2,3]\)、\([4,5,6]\)，到 \(5\) 时组合失败。

因为分割的子序列连接后也能满足要求，但是一个长的序列分割成子序列却不一定满足要求。

下列代码中的两个判断条件（第 11 行和第 15 行）先后顺序不能交换。

from collections import Counter, defaultdict
from typing import List

class Solution:
    def isPossible(self, nums: List[int]) -> bool:
        count = Counter(nums)  # 每个数字出现的次数
        end = defaultdict(int)  # 以 x 结尾的序列

        for i, x in enumerate(nums):
            if count[x]:
                if end[x - 1]: # 情况 1
                    count[x] -= 1
                    end[x - 1] -= 1
                    end[x] += 1
                elif count[x + 1] and count[x + 2]: # 情况 4
                    count[x] -= 1
                    count[x + 1] -= 1
                    count[x + 2] -= 1
                    end[x + 2] += 1
                else:
                    return False
        return True

659. 分割数组为连续子序列#

问题描述#

解题思路#

659. 分割数组为连续子序列 #