不要擺，沒事干就刷題，只有好處，沒有壞處，實在不行，看看競賽題

面試經典 150 題 - 2

面試經典 150 題

210. 課程表 II

210. 課程表 II

• 一眼拓撲排序. 好久沒寫過拓撲排序了，寫得特別糟糕

public int[] findOrder(int n, int[][] prerequisites) {int[] order = new int[n];if (prerequisites == null) {for (int i = 0; i < n; i++) order[i] = i;return order;}// 創建鄰接表 和 入度數組ArrayList<ArrayList<Integer>> adj = new ArrayList<>();for (int i = 0; i < n; i++) {adj.add(new ArrayList<>());}int[] inDegree = new int[n];for (int[] prerequisite : prerequisites) {adj.get(prerequisite[1]).add(prerequisite[0]);inDegree[prerequisite[0]]++;}// 入度隊列 （不需要棧）Stack<Integer> s = new Stack<>();for (int i = 0; i < inDegree.length; i++) {if (inDegree[i] == 0) s.push(i);}// 拓撲排序int cnt = 0;for (int i = 0; i < n; i++) {if (s.isEmpty()) break;Integer pop = s.pop();order[cnt++] = pop;for (Integer x : adj.get(pop)) {inDegree[x]--;if (inDegree[x] == 0) {s.push(x);}}}if (cnt < n) return new int[0];return order;
}

• 看了下大佬的做法，發現確實有幾處值得修改

主要就是度為0的不必非要用棧，用隊列也行，隊列直接作為拓撲排序的終止條件即可
沒有前置關系時不需要要特判，全是度為0的節點，也可以照常執行
不要用statck，繼承了Vector, 有很多鎖，效率很低

修改后4ms,差不多了吧

public int[] findOrder(int n, int[][] prerequisites) {// 創建鄰接表 和 入度數組ArrayList<ArrayList<Integer>> adj = new ArrayList<>();for (int i = 0; i < n; i++) adj.add(new ArrayList<>());int[] inDegree = new int[n];for (int[] prerequisite : prerequisites) {adj.get(prerequisite[1]).add(prerequisite[0]);inDegree[prerequisite[0]]++;}// 入度隊列 （不需要棧）Deque<Integer> q = new LinkedList<>();for (int i = 0; i < inDegree.length; i++) {if (inDegree[i] == 0) q.offer(i);}// 拓撲排序int[] order = new int[n];int cnt = 0;while (!q.isEmpty()){Integer pop = q.poll();order[cnt++] = pop;for (Integer x : adj.get(pop)) {inDegree[x]--;if (inDegree[x] == 0) q.push(x);}}if (cnt < n) return new int[0];return order;
}