难度: Medium
Submission
运行时间: 82 ms
内存: 19.6 MB
class Solution:
def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:
n = len(nums)
nexts = [[] for _ in range(n+1)]
inDegrees = [0]*(n+1)
inDegrees[0] = inf
for seq in sequences:
for prev, nex in zip(seq, seq[1:]):
nexts[prev].append(nex)
inDegrees[nex] += 1
if inDegrees[nums[0]]: return False
q = deque(i for i, v in enumerate(inDegrees) if not v)
if len(q) > 1: return False
it = iter(nums)
while q:
i = q.popleft()
if i != next(it, None): return False
batch = 0
for nex in nexts[i]:
inDegrees[nex] -= 1
if not inDegrees[nex]:
q.append(nex)
batch += 1
if batch > 1: return False
return True
Explain
这个题解使用了拓扑排序的思路。首先根据给定的序列构建有向图，然后对图进行拓扑排序，判断拓扑排序的结果是否与给定的 nums 数组相同。在构建有向图时，使用 nexts 数组记录每个节点的后继节点，使用 inDegrees 数组记录每个节点的入度。在拓扑排序时，使用队列 q 存储入度为 0 的节点，每次从队列中取出一个节点，将其与 nums 数组中的元素进行比较，然后将其所有后继节点的入度减 1，如果入度变为 0，则将后继节点加入队列。如果在排序过程中出现了与 nums 数组不一致的情况，或者在某一轮中入度变为 0 的节点数量大于 1，则说明给定的序列无法唯一确定一个超序列，返回 False。最后，如果拓扑排序成功完成，且 nums 数组中的所有元素都被访问到，则说明可以重建出唯一的超序列，返回 True。
时间复杂度: O(n+m)
空间复杂度: O(n)
class Solution:
def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:
n = len(nums)
nexts = [[] for _ in range(n+1)] # 记录每个节点的后继节点
inDegrees = [0]*(n+1) # 记录每个节点的入度
inDegrees[0] = inf # 将节点 0 的入度设为正无穷，避免其被加入队列
for seq in sequences:
for prev, nex in zip(seq, seq[1:]):
nexts[prev].append(nex)
inDegrees[nex] += 1
if inDegrees[nums[0]]: return False # 如果 nums 的第一个元素的入度不为 0，则无法重建超序列
q = deque(i for i, v in enumerate(inDegrees) if not v) # 初始时将所有入度为 0 的节点加入队列
if len(q) > 1: return False # 如果初始时入度为 0 的节点数量大于 1，则无法唯一确定超序列
it = iter(nums)
while q:
i = q.popleft()
if i != next(it, None): return False # 如果当前节点与 nums 中的元素不一致，则无法重建超序列
batch = 0
for nex in nexts[i]:
inDegrees[nex] -= 1
if not inDegrees[nex]:
q.append(nex)
batch += 1
if batch > 1: return False # 如果在某一轮中入度变为 0 的节点数量大于 1，则无法唯一确定超序列
return True # 拓扑排序成功完成，且 nums 中的所有元素都被访问到，因此可以重建出唯一的超序列
Explore
在拓扑排序中，nexts数组用于存储图中每个节点的所有后继节点，这使得每次处理完一个节点后，可以迅速找到所有由此节点直接指向的后继节点，并更新这些后继节点的状态（例如减少其入度）。而inDegrees数组用于记录每个节点的入度数，即指向该节点的边的数量。入度为0的节点表示没有任何前置条件，可以立即处理。这两个数组共同支持了拓扑排序的实现：通过inDegrees来确定处理顺序，通过nexts来更新相关节点的状态。
如果初始时入度为0的节点数量大于1，这意味着有多个节点可以作为序列的起始点，从而可能形成不同的序列排列。在序列重建的上下文中，目标是确认是否可以通过给定的序列片段唯一地重建一个超序列。如果存在多个可能的起始节点，这表明给定的序列片段没有足够的信息来确定一个唯一的序列，因此算法会返回False，指出无法唯一确定一个超序列。
拓扑排序的目的是确定节点的唯一线性顺序。在序列重建问题中，如果拓扑排序过程中的当前节点与预期的nums数组中的元素不一致，这意味着重建的序列与给定的目标序列nums不匹配。由于我们的目标是验证是否可以根据给定的序列片段精确地重建nums，任何不一致都会直接导致重建失败。不存在其他可能的情况允许继续拓扑排序，因为序列已经偏离了唯一的目标序列，继续排序不会恢复其与nums的一致性。
在严格的序列重建问题中，如果在某一轮中入度变为0的节点数量大于1，这意味着序列的下一步有多个可能的选择，从而无法唯一确定超序列。通常情况下，这直接导致返回False。如果问题允许多个合法序列，可以考虑所有可能的路径，并尝试每一条路径是否能最终重建为唯一序列。然而，在本题的目的是验证是否可以从给定的序列片段唯一地重建超序列，因此没有其他策略可以继续尝试重建超序列，而只能判断为无法重建。