Leetcode 剑指 Offer II 115.序列重建
题目难度: 中等
今天继续更新 Leetcode 的剑指 Offer（专项突击版）系列, 大家在公众号 算法精选 里回复
剑指offer2就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述
给定一个长度为 n 的整数数组 nums ，其中 nums 是范围为 [1，n] 的整数的排列。还提供了一个 2D 整数数组 sequences ，其中 sequences[i] 是 nums 的子序列。 检查 nums 是否是唯一的最短 超序列 。最短 超序列 是 长度最短 的序列，并且所有序列 sequences[i] 都是它的子序列。对于给定的数组 sequences ，可能存在多个有效的 超序列 。
- 例如，对于 sequences = [[1,2],[1,3]] ，有两个最短的 超序列 ，[1,2,3] 和 [1,3,2] 。
- 而对于 sequences = [[1,2],[1,3],[1,2,3]] ，唯一可能的最短 超序列 是 [1,2,3] 。[1,2,3,4] 是可能的超序列，但不是最短的。
如果 nums 是序列的唯一最短 超序列 ，则返回 true ，否则返回 false 。 子序列 是一个可以通过从另一个序列中删除一些元素或不删除任何元素，而不改变其余元素的顺序的序列。
示例 1：
- 输入：nums = [1,2,3], sequences = [[1,2],[1,3]]
- 输出：false
- 解释：有两种可能的超序列：[1,2,3]和[1,3,2]。
- 序列 [1,2] 是[1,2,3]和[1,3,2]的子序列。
- 序列 [1,3] 是[1,2,3]和[1,3,2]的子序列。
- 因为 nums 不是唯一最短的超序列，所以返回 false。
示例 2：
- 输入：nums = [1,2,3], sequences = [[1,2]]
- 输出：false
- 解释：最短可能的超序列为 [1,2]。
- 序列 [1,2] 是它的子序列：[1,2]。
- 因为 nums 不是最短的超序列，所以返回 false。
示例 3：
- 输入：nums = [1,2,3], sequences = [[1,2],[1,3],[2,3]]
- 输出：true
- 解释：最短可能的超序列为[1,2,3]。
- 序列 [1,2] 是它的一个子序列：[1,2,3]。
- 序列 [1,3] 是它的一个子序列：[1,2,3]。
- 序列 [2,3] 是它的一个子序列：[1,2,3]。
- 因为 nums 是唯一最短的超序列，所以返回 true。
提示：
- n == nums.length
- 1 <= n <= 10^4
- nums 是 [1, n] 范围内所有整数的排列
- 1 <= sequences.length <= 10^4
- 1 <= sequences[i].length <= 10^4
- 1 <= sum(sequences[i].length) <= 10^5
- 1 <= sequences[i][j] <= n
- sequences 的所有数组都是 唯一 的
- sequences[i] 是 nums 的一个子序列
题目思考
- 需要使用什么算法和数据结构?
解决方案
- 分析题目, nums 要想是唯一的最短超序列, 需要满足三件事情: 1. 所有序列 sequences[i] 都是它的子序列; 2. 它是最短的超序列; 3. 它是唯一的
- 其中对于第一点题目已经已经给出, 只需要判断后两点即可, 如何判断呢?
- 我们可以逆向思考, 从给出的子序列 sequences 出发, 从它们开始构建超序列, 如果只能构建出一个, 且跟 nums 完全一致, 则说明 nums 是唯一的最短超序列
- 既然每个 sequences 都给出了其数字顺序, 我们可以根据它们建立一个有向图, 并维护其入度, 例如子序列
[1,2,3], 则1->2,2->3,1,2,3的入度分别为0,1,1 - 等找到所有数字的指向关系和入度后, 我们就可以将问题转换成之前类似的拓扑排序的思路, 先加入顺序最小(入度为 0)的数字, 再加入顺序第二小的数字, 以此类推, 大家可以参考上上周文章Leetcode 剑指 Offer II 113.课程表 II的思考过程
- 不过这里需要保证构造出的序列和 nums 完全一致且唯一, 所以我们在构造过程中, 需要额外维护当前 nums 下标且每次只能加入一个数字: 如果当前数字和 nums 不一致, 说明 nums 不是最短超序列; 如果有多个数字可以加入, 也说明 nums 不是唯一的最短超序列
- 举个例子, 对于
nums = [1,2,3], sequences = [[1,2],[1,3],[2,3]], 我们在遍历子序列后, 可以得到以下的大小关系:1->2,1->3,2->3- 首先 1 的入度为 0, 所以先加入 1;
- 然后 2 的入度变成 0, 所以加入 2;
- 最后 3 的入度变成 0, 所以加入 3;
- 其顺序和 nums 完全一致, 所以 nums 是唯一的最短超序列
- 再举个例子, 对于
nums = [1,2,3], sequences = [[1,2],[1,3],[3,2]], 我们在遍历子序列后, 可以得到以下的大小关系:1->2,1->3,3->2- 首先 1 的入度为 0, 所以先加入 1;
- 然后 3 的入度变成 0, 所以加入 3;
- 最后 2 的入度变成 0, 所以加入 2;
- 其顺序和 nums 不一致, 所以 nums 不是唯一的最短超序列
- 再再举个例子, 对于
nums = [1,2,3], sequences = [[1,2],[1,3]], 我们在遍历子序列后, 可以得到以下的大小关系:1->2,1->3- 首先 1 的入度为 0, 所以先加入 1;
- 然后 2 和 3 的入度都变成 0, 所以既可以先加入 2, 也可以先加入 3;
- 也就是说存在两个最短超序列
[1,2,3]和[1,3,2], 所以 nums 不是唯一的最短超序列
- 具体代码实现时, 分为以下四步:
- 首先遍历所有子序列, 根据其相邻位置的数字, 建立大小关系和入度, 这里使用集合避免重复添加相同的有向边
- 然后遍历 1~n 所有数字, 找出入度为 0 的数字, 加入队列中, 并维护当前 nums 下标, 初始化为 0
- 接下来遍历队列中当前可以处理的数字, 如果可用数字多于 1 个, 则说明超序列不唯一, 返回 false; 如果当前数字不等于 nums[i], 则说明 nums 不匹配, 也返回 false
- 然后利用大小关系找出这些数字指向的数字, 将它们入度减 1, 如果某个数字入度变成了 0, 则代表它的顺序确定了, 将其加入队列中, 并等待后续遍历处理
- 最后遍历结束时, 说明子序列构造出来的最短超序列和 nums 完全一致且唯一, 直接返回 true
- 下面的代码对必要步骤有详细的解释, 方便大家理解
复杂度
- 时间复杂度
O(N+M): nums 长度是 N, sequences 的所有子序列长度之和是 M, 构造图和拓扑排序时都需要O(N+M) - 空间复杂度
O(N+M): maps 存O(N+M), indegree 和 q 都存O(N)
代码
class Solution:
def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:
### 拓扑排序
n = len(nums)
maps = [set() for _ in range(n + 1)]
indegree = [0] * (n + 1)
for seq in sequences:
for i in range(1, len(seq)):
pre, cur = seq[i - 1], seq[i]
if cur not in maps[pre]:
# 注意使用集合避免重复添加!!!
maps[pre].add(cur)
indegree[cur] += 1
q = []
for i in range(1, n + 1):
if indegree[i] == 0:
q.append(i)
i = 0
while q:
if len(q) != 1:
# 如果当前可以使用的节点不是1, 则说明有多个最短超序列, 不是唯一
return False
if i >= n or q[0] != nums[i]:
# 如果当前节点不等于nums[i], 说明nums不是最短超序列
return False
cur = q.pop()
i += 1
for nex in maps[cur]:
indegree[nex] -= 1
if indegree[nex] == 0:
# nex的入度变成了0, 可以处理它了
q.append(nex)
return True
大家可以在下面这些地方找到我~😊
我的公众号: 算法精选, 欢迎大家扫码关注~😊
