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];
}
}