210. 课程表 II

1. 题目

  • 现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。

    • 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。

    返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。

    示例 1：

    1
    2
    3
    输入：numCourses = 2, prerequisites = [[1,0]]
    输出：[0,1]
    解释：总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。

    示例 2：

    1
    2
    3
    4
    输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
    输出：[0,2,1,3]
    解释：总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
    因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。

    示例 3：

    1
    2
    输入：numCourses = 1, prerequisites = []
    输出：[0]

    提示：

    • 1 <= numCourses <= 2000
    • 0 <= prerequisites.length <= numCourses * (numCourses - 1)
    • prerequisites[i].length == 2
    • 0 <= ai, bi < numCourses
    • ai != bi
    • 所有[ai, bi] 互不相同

2. 思路

  • 整体思路同207. 课程表，仅仅是在拓扑排序的过程中，记录下课程的学习顺序
  • 利用拓扑排序进行记录时，需要注意的是从队列中取出的节点均为最不受限制的课程（即无入度），因此在记录的过程中呈现倒序记录
  • 完成记录后，如果结果数组下标不为-1，则说明有向图中存在环导致课程表无法进行顺序学习

3. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        var edgeMap = new HashMap<Integer, List<Integer>>(numCourses);
        var inCount = new int[numCourses];

        var result = new int[numCourses];
        var index = numCourses - 1;

        for (var prerequisite : prerequisites) {
            var source = prerequisite[0];
            var target = prerequisite[1];

            inCount[target]++;

            var targetEdges = edgeMap.getOrDefault(source, new ArrayList<Integer>());
            targetEdges.add(target);
            edgeMap.put(source, targetEdges);
        }

        var queue = new ArrayDeque<Integer>();

        for (var i = 0; i < numCourses; ++i) {
            if (inCount[i] == 0) {
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) {
            var node = queue.poll();
            var targetEdges = edgeMap.getOrDefault(node, Collections.emptyList());

            for (var target : targetEdges) {
                inCount[target]--;

                if (inCount[target] == 0) {
                    queue.offer(target);
                }
            }

            result[index] = node;
            index--;
        }

        return index >= 0 ? new int[0] : result;
    }
}

4. 复杂度

  • 时间复杂度: O(E + V)，时间上最长需要遍历所有有向图的边 + 节点，因此时间复杂度为O(E + V)
  • 空间复杂度: O(E + V)

image-20231124145031718