九章算法 | Amazon面试题：安排课程

你需要去上n门九章的课才能获得offer，这些课被标号为 ​0​ 到 ​n-1​ 。

有一些课程需要“前置课程”，比如如果你要上课程0，你需要先学课程1，我们用一个匹配来表示他们： ​[0,1]​

给你课程的总数量和一些前置课程的需求，返回你为了学完所有课程所安排的学习顺序。

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

在线评测地址：LintCode 领扣

例1:

输入: n = 2, prerequisites = [[1,0]] 
输出: [0,1] 

例2:

输入: n = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] 
输出: [0,1,2,3] or [0,2,1,3] 

解题思路

对于两门课之间的约束关系，很容易联想到图，我们可以将课抽象为节点，将约束抽象为一条有向边，可以用有向图的相关算法解决问题。拓扑排序正好可以解决这一问题。

算法：拓扑排序

一个合法的选课序列就是一个拓扑序，拓扑序是指一个满足有向图上，不存在一条边出节点在入节点后的线性序列，如果有向图中有环，就不存在拓扑序。可以通过拓扑排序算法来得到拓扑序，以及判断是否存在环。

拓扑排序步骤：

1. 建图并记录所有节点的入度。
2. 将所有入度为​0​的节点加入队列。
3. 取出队首的元素​now​，将其加入拓扑序列。
4. 访问所有​now​的邻接点​nxt​，将​nxt​的入度减​1​，当减到​0​后，将​nxt​加入队列。
5. 重复步骤​3​、​4​，直到队列为空。
6. 如果拓扑序列个数等于节点数，代表该有向图无环，且存在拓扑序。

复杂度分析

设课程数，即图的节点数为V。

约束数量，即图的边数为E。

时间复杂度​O(V + E)​

• 建图，扫描一遍所有的边​O(E)​。
• 每个节点最多入队出队​1​次，复杂度​O(V)​。
• 邻接表最终会被遍历​1​遍，复杂度​O(E)​。
• 综上，总复杂度为​O(V + E)​。

空间复杂度​O(V + E)​

• 邻接表占用​O(V + E)​的空间。
• 队列最劣情况写占用​O(V)​的空间。
• 综上，总复杂度为​O(V + E)​。

public class Solution {
    /*
     * @param numCourses: a total of n courses
     * @param prerequisites: a list of prerequisite pairs
     * @return: the course order
     */
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List[] graph = new ArrayList[numCourses];
        int[] inDegree = new int[numCourses];
        
        for (int i = 0; i < numCourses; i++) {
            graph[i] = new ArrayList<Integer>();
        }
        
        // 建图
        for (int[] edge: prerequisites) {
            graph[edge[1]].add(edge[0]);
            inDegree[edge[0]]++;
        }
        
        int numChoose = 0;
        Queue queue = new LinkedList();
        int[] topoOrder = new int[numCourses];
        
        // 将入度为 0 的编号加入队列
        for(int i = 0; i < inDegree.length; i++){
            if (inDegree[i] == 0) {
                queue.add(i);
            }
        }
        
        while (! queue.isEmpty()) {
            int nowPos = (int)queue.poll();
            topoOrder[numChoose] = nowPos;
            numChoose++;
            // 将每条边删去，如果入度降为 0，再加入队列
            for (int i = 0; i < graph[nowPos].size(); i++) {
                int nextPos = (int)graph[nowPos].get(i);
                inDegree[nextPos]--;
                if (inDegree[nextPos] == 0) {
                    queue.add(nextPos);
                }
            }
        }
        
        if (numChoose == numCourses)
            return topoOrder;
        return new int[0];
    }
}

更多题解参考：九章算法