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

• 3：然后就是新建一个队列用来一个一个存放入度为0的点，下面这个代码其实作用就是第一次将一开始入度为0的点先存进去：

        Deque<Integer> q = new LinkedList();for(int i = 0;i<inDegree.length;i++){if(inDegree[i]==0){q.offer(i);}}

• 4：只要队列不为空，我们就一直循环下去，先去出队列里面的元素放入结果数组中，然后删掉这个元素的指出去的边：

  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)$

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