题目分析

本题是308周周赛的第四题，有一定的难度，考察了拓扑排序的知识点，给定一个有向图，能否将这个图进行排序。

拓扑排序

我们先分析这个题目，rowConditions和colConditions表示行和列之间的关系。比如[2, 3]，2出现的行数在3出现的行数之前。

而且我们可以推出本题的行和列是相互独立的，假设行是[1, 3, 2]，列可以是任意的

比如列是[1, 3, 2]，则结果为

$$ \begin{bmatrix} 1 & 0 & 0 \\ 0 & 3 & 0 \\ 0 & 0 & 2 \end{bmatrix} $$

比如列是[3, 1, 2]，则结果为

$$ \begin{bmatrix} 0 & 1 & 0 \\ 3 & 0 & 0 \\ 0 & 0 & 2 \end{bmatrix} $$

比如列是[3, 2, 1]，则结果为

$$ \begin{bmatrix} 0 & 0 & 1 \\ 3 & 0 & 0 \\ 0 & 2 & 0 \end{bmatrix} $$

因此我们要做的是根据行和列的关系，找到从大到小排序的数组。然后根据x，找到x所在的行和列的索引，放在相应的位置即可。

在根据有向图寻找排序数组的过程，我们称之为拓扑排序，就是将图进行排序。

拓扑排序的思路类似于BFS，用degree表示入度的值，有x条边指向某个节点，某个节点的入度就是x。入度为0的点，说明是最起始的点，可以将其排在最大值。因为没有边指向该点，所以没有点大于它。

因此先将入度为0的点加入到队列中，然后开始遍历，找到某个点，将某个点的入度-1，如果入度更新到0，也将其加入到队列中，先加入队列的元素是排在前面的序号，因此加入到队列的同时，也要添加到拓扑排序的结果数组中。

算法的时间复杂度为$ O(k \times max(m, n)) $，空间复杂度为O(max(k^2, m, n))。

class Solution {
    public int[][] buildMatrix(int k, int[][] rowConditions, int[][] colConditions) {
        List<Integer> rowTopSort = getTopSort(rowConditions, k);
        List<Integer> colTopSort = getTopSort(colConditions, k);
        if (rowTopSort.size() != k || colTopSort.size() != k) {
            return new int[][]{};
        }
        int[][] res = new int[k][k];
        for (int i = 0; i < k; i++) {
            int rowIndex = getIndex(rowTopSort, i);
            int colIndex = getIndex(colTopSort, i);
            res[rowIndex][colIndex] = i + 1;
        }
        return res;
    }

    private int getIndex(List<Integer> topSort, int x) {
        for (int i = 0; i < topSort.size(); i++) {
            if (topSort.get(i) == x) {
                return i;
            }
        }
        return -1;
    }

    private List<Integer> getTopSort(int[][] conditions, int k) {
        List<Integer> res = new ArrayList<>();
        List<Set<Integer>> relations = new ArrayList<>();
        int[] degree = new int[k];
        for (int i = 0; i < k; i++) {
            relations.add(new HashSet<>());
        }
        for (int[] condition : conditions) {
            int out = condition[0] - 1;
            int in = condition[1] - 1;
            if (!relations.get(out).contains(in)) {
                relations.get(out).add(in);
                degree[in]++;
            }
        }
        LinkedList<Integer> queue = new LinkedList<>();
        for (int i = 0; i < k; i++) {
            if (degree[i] == 0) {
                queue.add(i);
                res.add(i);
            }
        }
        while (!queue.isEmpty()) {
            int cur = queue.removeFirst();
            for (int x : relations.get(cur)) {
                if (--degree[x] == 0) {
                    queue.add(x);
                    res.add(x);
                }
            }
        }
        return res;
    }
}

刷题总结

今天又学习到了新知识——拓扑排序，小伙伴们课后一定要多加巩固，找一些拓扑排序的题目练手。