Problem: 210. 课程表 II
文章目录
思路
首先这道题是一道经典的拓扑排序题目,那么什么是拓扑排序呢?举例说明:
在上图中,左边这个图我们首先一个一个点的去判断他们的入度是多少,从左到右就是 (0:0),(1:1),(2:1),(3:2),然后我们先找到入度为0的点接下来删除掉这个点以及他指出去的边,然后重复这个过程,一个一个输出那些入度为0的点,这个图最终的拓扑排序就是:0,1,2,3或者0,2,1,3这样,那么知道了拓扑排序再来看这道题就很简单了
解题方法
-
1:首先新建一个inDegree数组用来存放所有的点的入度:
int[] inDegree = new int[numCourses];
-
2:然后遍历所有子数组将所有点及其入度存进去,这道题就是课程号本身为坐标,对应的值就是入度的数量:
for(int[] edges :prerequisites){
inDegree[edges[0]]++;
}
Deque<Integer> q = new LinkedList();
for(int i = 0;i<inDegree.length;i++){
if(inDegree[i]==0){
q.offer(i);
}
}
int[] res = new int[numCourses];
int index = 0;
while(!q.isEmpty()){
int node = q.poll();
res[index++] = node;
for(int[] edges : prerequisites){
if(edges[1]==node){
inDegree[edges[0]]--;
if(inDegree[edges[0]]==0){
q.offer(edges[0]);
}
}
}
}
复杂度
- 时间复杂度:
添加时间复杂度, 示例: O ( n ) O(n) O(n)
- 空间复杂度:
添加空间复杂度, 示例: O ( n ) O(n) O(n)
Code
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
int[] inDegree = new int[numCourses];
for(int[] edges :prerequisites){
inDegree[edges[0]]++;
}
Deque<Integer> q = new LinkedList();
for(int i = 0;i<inDegree.length;i++){
if(inDegree[i]==0){
q.offer(i);
}
}
int[] res = new int[numCourses];
int index = 0;
while(!q.isEmpty()){
int node = q.poll();
res[index++] = node;
for(int[] edges : prerequisites){
if(edges[1]==node){
inDegree[edges[0]]--;
if(inDegree[edges[0]]==0){
q.offer(edges[0]);
}
}
}
}
return index == numCourses? res:new int[0];
}
}