本文最后更新于 392 天前,其中的信息可能已经有所发展或是发生改变。
题目描述:
现在你总共有 numCourses
门课需要选,记为 0
到 numCourses - 1
。给你一个数组 prerequisites
,其中 prerequisites[i] = [ai, bi]
,表示在选修课程 ai
前 必须 先选修 bi
。
- 例如,想要学习课程
0
,你需要先完成课程1
,我们用一个匹配来表示:[0,1]
。
返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序,你只要返回 任意一种 就可以了。如果不可能完成所有课程,返回 一个空数组 。
示例 1:
输入:numCourses = 2, prerequisites = [[1,0]]
输出:[0,1]
解释:总共有 2 门课程。要学习课程 1,你需要先完成课程 0。因此,正确的课程顺序为 [0,1] 。
示例 2:
输入: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:
输入: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]
互不相同
解法一:拓扑排序
算法思路:
本题与 207. 课程表 – 拓扑排序 思路基本一致,不同之处在于将每次选择的课都记录在一个List当中,然后返回这个List即可。
代码实现:
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
int[] inDegree = new int[numCourses]; // 入度数组
HashMap<Integer, List<Integer>> map = new HashMap<>(); // 邻接表
List<Integer> result = new ArrayList<Integer>(); // 答案List
// 构建入度数组和邻接表
for (int i = 0; i < prerequisites.length; i++) {
inDegree[prerequisites[i][0]]++; // 求课的初始入度值
if (map.containsKey(prerequisites[i][1])) { // 当前课已经存在于邻接表
map.get(prerequisites[i][1]).add(prerequisites[i][0]); // 添加依赖它的后续课
} else { // 当前课不存在于邻接表
List<Integer> list = new ArrayList<>();
list.add(prerequisites[i][0]);
map.put(prerequisites[i][1], list);
}
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < inDegree.length; i++) { // 所有入度为0的课入列
if (inDegree[i] == 0) {
queue.offer(i);
}
}
int count = 0;
while (!queue.isEmpty()) {
int selected = queue.poll(); // 当前选的课,出列
result.add(selected); // 记录下已选的课
count++; // 选课数+1
List<Integer> toEnQueue = map.get(selected); // 获取这门课对应的后续课
if (toEnQueue != null && !toEnQueue.isEmpty()) { // 确实有后续课
for (int i = 0; i < toEnQueue.size(); i++) {
int dependentCourse = toEnQueue.get(i);
inDegree[dependentCourse]--; // 依赖它的后续课的入度-1
if (inDegree[dependentCourse] == 0) { // 如果因此减为0,入列
queue.offer(dependentCourse);
}
}
}
}
// List to int Array
int[] resultArr = result.stream()
.mapToInt(Integer::intValue)
.toArray();
return resultArr.length == numCourses ? resultArr : new int[0]; //如果已选的课门数等于numCourses,返回上课顺序,否则返回空数组
}
}
复杂度分析:
时间复杂度: O(n + m)
空间复杂度: O(n + m)