序列重建

标签: 图 拓扑排序 数组

难度: Medium

给定一个长度为 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 <= 104
  • nums 是 [1, n] 范围内所有整数的排列
  • 1 <= sequences.length <= 104
  • 1 <= sequences[i].length <= 104
  • 1 <= sum(sequences[i].length) <= 105
  • 1 <= sequences[i][j] <= n
  • sequences 的所有数组都是 唯一 的
  • sequences[i] 是 nums 的一个子序列

注意：本题与主站 444 题相同：https://leetcode-cn.com/problems/sequence-reconstruction/

Submission

运行时间: 71 ms

内存: 19.4 MB

class Solution:
    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:
        n=len(nums)
        indegree=[1]+[0]*n
        g=[[] for _ in range(n+1)]
        for seq in sequences:
            for a,b in pairwise(seq):
                indegree[b]+=1
                g[a].append(b)
        
        q=deque([i for i in range(n+1) if indegree[i]==0])
        if len(q)>1:
            return False
        num=0
        while q:
            node=q.popleft()
            num+=1
            for neighbor in g[node]:
                indegree[neighbor]-=1
                if indegree[neighbor]==0:
                    q.append(neighbor)
            if len(q)>1:
                return False
        return num==n

Explain

这个题解使用了拓扑排序的思路来解决问题。首先，构建一个有向图和每个节点的入度表。遍历给定的序列，对于序列中相邻的元素a和b，将a指向b的边添加到图中，并且b的入度加1。然后，使用一个队列来进行拓扑排序。初始时，将所有入度为0的节点加入队列。在拓扑排序的过程中，每次从队列中取出一个节点，然后遍历其所有相邻的节点，将这些节点的入度减1，如果某个相邻节点的入度变为0，则将其加入队列。如果在任何时刻队列中有多于一个节点，说明存在多个可能的序列，返回false。最后，如果遍历的节点数等于n，则说明给定的序列可以唯一确定一个序列，返回true，否则返回false。

时间复杂度: O(n + sum(sequences[i].length))

空间复杂度: O(n + sum(sequences[i].length))

class Solution:
    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:
        n=len(nums)
        indegree=[1]+[0]*n  # 初始化入度表
        g=[[] for _ in range(n+1)]  # 初始化邻接表
        for seq in sequences:
            for a,b in pairwise(seq):  # 构建图和入度表
                indegree[b]+=1
                g[a].append(b)
        
        q=deque([i for i in range(n+1) if indegree[i]==0])  # 入度为0的节点入队
        if len(q)>1:  # 如果有多于一个入度为0的节点，则不唯一
            return False
        num=0  # 记录遍历的节点数
        while q:
            node=q.popleft()
            num+=1
            for neighbor in g[node]:  # 更新相邻节点的入度
                indegree[neighbor]-=1
                if indegree[neighbor]==0:
                    q.append(neighbor)
            if len(q)>1:  # 如果有多于一个入度为0的节点，则不唯一
                return False
        return num==n  # 如果遍历的节点数等于n，则唯一确定

Explore

题解中并没有明确说明如何避免重复添加边a到b。在实际实现中，可以通过检查是否已经存在从a到b的边来避免重复添加。这可以通过在构建图时，为每个节点维护一个集合来存储其所有邻接点，并在添加边之前检查目标节点b是否已存在于节点a的邻接集合中。如果不存在，则添加边并更新入度，如果已存在，则忽略。这样可以确保每条边只被添加一次，从而防止重复添加。

在拓扑排序中，队列中同时存在多于一个节点的情况意味着图中存在多个节点同时没有任何入边，即有多个节点可以作为排序的下一个节点。这表明存在多种不同的顺序来进行节点的遍历，从而构造出多种不同的序列。因此，如果目标是确定一个序列是否能唯一地重建原始序列，那么在任何时刻队列中有多于一个入度为0的节点就会使得原始序列不能被唯一确定，因为这表示有多种可能的序列可以符合给定的顺序限制。

在拓扑排序中，如果所有的节点都被遍历一次且遍历的节点数正好等于n（序列中的元素数量），这意味着整个图是连通的且没有未解决的依赖（即不存在任何剩余的入边）。这种情况下，如果我们能够从一个节点开始，按照一定的顺序访问所有节点而没有任何剩余的入边，就可以确定这样的顺序是符合所有给定的序列限制的。如果节点数小于n，则说明有些节点由于环或其他依赖未被解决而未被访问，这表明序列无法通过给定的依赖关系唯一确定。