LeetCode 444. 序列重建

约 6 分钟
文章信息 7 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 会员题 1-2 字节
标签
数组 图 拓扑排序

题目描述

✅ 444. 序列重建

题意分析

给定原序列 org 和若干子序列 seqs，判断这些子序列提供的先后关系能否唯一确定 org。不仅要与原序列顺序相容，还要覆盖全部元素，并排除其他合法的排列顺序。

解法：拓扑排序判唯一

核心思路

[!blue]

把每个出现过的值作为节点，子序列中相邻的 a、b 建边 a -> b，表示 a 必须在 b 前。相邻关系的传递性已经包含同一子序列中的其他先后约束，因此符合全部约束的排列就是图的拓扑序。单元素子序列虽没有边，也必须登记对应节点。

拓扑排序每次从未处理节点中选择入度为 0 的节点。如果有多个候选，它们没有相互依赖的先后关系，不能唯一确定下一项；如果恰好一个，这一项就被强制确定。取出的节点还必须等于 org 当前项，保证唯一顺序确实是题目给定的原序列。

如果队列提前为空，剩余节点无法解除依赖，说明存在环，不能重建。只有每步都唯一、逐项都匹配，并且处理了全部节点，才能返回 true。最初的节点数量检查排除覆盖不足，逐项比较则进一步排除值不一致或顺序不同。

多条子序列可能给出同一条边。代码用集合去重，只有首次加边时才增加入度，后续删边也只减一次，保证入度始终等于尚未解除的不同前驱数量。

解题步骤

  1. 登记子序列中的所有值，初始化邻接集合和入度；不同值的数量与 org 长度不同时返回 false。
  2. 加入每条子序列的相邻边，只在边首次出现时增加后继入度。
  3. 将所有零入度节点入队，令原序列下标 idx = 0。
  4. 每轮要求队列中未处理候选恰好一个，取出后与 org[idx] 比较；不一致就返回 false。
  5. 增加 idx，将当前节点所有后继的入度减一，降到 0 的后继入队。
  6. 队列耗尽后，只有 idx == org.length 才返回 true。

代码实现

class Solution {
    public boolean sequenceReconstruction(int[] org, List<List<Integer>> seqs) {
        Map<Integer, Set<Integer>> graph = new HashMap<>();
        Map<Integer, Integer> indegree = new HashMap<>();

        for (List<Integer> seq : seqs) {
            for (int v : seq) {
                graph.putIfAbsent(v, new HashSet<>());
                indegree.putIfAbsent(v, 0);
            }
        }

        if (indegree.size() != org.length) {
            return false;
        }

        for (List<Integer> seq : seqs) {
            for (int i = 1; i < seq.size(); i++) {
                int a = seq.get(i - 1);
                int b = seq.get(i);

                // 邻接集合只保留一份边，入度也只在首次加边时增加。
                if (graph.get(a).add(b)) {
                    indegree.put(b, indegree.get(b) + 1);
                }
            }
        }

        Queue<Integer> queue = new ArrayDeque<>();

        for (int v : indegree.keySet()) {
            if (indegree.get(v) == 0) {
                queue.offer(v);
            }
        }

        int idx = 0;

        while (!queue.isEmpty()) {
            // 当前必须只有一个候选，多个候选不能唯一确定下一项。
            if (queue.size() != 1) {
                return false;
            }

            int cur = queue.poll();

            if (idx >= org.length || cur != org[idx]) {
                return false;
            }

            idx++;

            for (int next : graph.get(cur)) {
                indegree.put(next, indegree.get(next) - 1);

                if (indegree.get(next) == 0) {
                    queue.offer(next);
                }
            }
        }

        // 还要确认全部节点已处理，队列提前空可能是存在环。
        return idx == org.length;
    }
}

func sequenceReconstruction(org []int, seqs [][]int) bool {
    graph := make(map[int]map[int]struct{})
    indeg := make(map[int]int)
    for _, seq := range seqs {
        for _, v := range seq {
            if _, ok := graph[v]; !ok {
                graph[v] = make(map[int]struct{})
            }
            if _, ok := indeg[v]; !ok {
                indeg[v] = 0
            }
        }
    }
    if len(indeg) != len(org) {
        return false
    }

    for _, seq := range seqs {
        for i := 1; i < len(seq); i++ {
            a := seq[i-1]
            b := seq[i]
            // 邻接集合只保留一份边，入度也只在首次加边时增加。
            if _, ok := graph[a][b]; !ok {
                graph[a][b] = struct{}{}
                indeg[b]++
            }
        }
    }

    queue := make([]int, 0)
    for v := range indeg {
        if indeg[v] == 0 {
            queue = append(queue, v)
        }
    }

    idx := 0
    head := 0
    for head < len(queue) {
        // 当前必须只有一个候选，多个候选不能唯一确定下一项。
        if len(queue)-head != 1 {
            return false
        }
        cur := queue[head]
        head++
        if idx >= len(org) || cur != org[idx] {
            return false
        }
        idx++

        for next := range graph[cur] {
            indeg[next]--
            if indeg[next] == 0 {
                queue = append(queue, next)
            }
        }
    }

    // 还要确认全部节点已处理，队列提前空可能是存在环。
    return idx == len(org)
}

复杂度分析

  • 时间复杂度：期望 $O(S+Q+V+E)$，S 为全部子序列元素总数，Q 为子序列数，V、E 为不同节点和去重边数；建图扫描全部输入，拓扑排序处理每个节点和不同边一次。
  • 空间复杂度：$O(V+E)$，保存图、入度与队列。

关键点总结

[!green]

  • 一个合法拓扑序不等于唯一拓扑序。
  • 集合去重与入度计数保持一致。
  • 结束时还需验证所有节点处理完，排除环或覆盖不足。
  • Go 队列用下标前进，当前候选数是 len(queue) - head，不能把已处理元素也算进去。

易错点总结

[!yellow]

  • 只验证子序列都能从 org 取出：没有证明唯一性。
  • 集合只存一份边，入度却按重复输入增加：后继无法正常归零。
  • 队列空就直接返回 true：图有环时也可能一开始为空。
  • 只比节点数量不比具体顺序和值：可能接受另一组元素或另一条顺序。

相似题目

题目 难度 关联与区别
210. 课程表 II 中等 原题只要任意拓扑序，本题还要求顺序唯一并与指定序列一致。
269. 火星词典 困难 同样从多个局部顺序构建偏序图，本题进一步检查每一步是否只有一个可选节点。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/76530639
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！