【LeetCode】308d：给定条件下构造矩阵

原题链接： 307d：给定条件下构造矩阵
记录一下学习过程。

题目大意

给你一个 正整数 k ，同时给你：
一个大小为 n 的二维整数数组 rowConditions ，其中rowConditions[i] = [abovei, belowi]和
一个大小为 m 的二维整数数组 colConditions ，其中 colConditions[i] = [lefti, righti] 。
两个数组里的整数都是 1 到 k 之间的数字。
你需要构造一个 k x k 的矩阵，1 到 k 每个数字需要 恰好出现一次 。剩余的数字都是 0 。
矩阵还需要满足以下条件：
对于所有 0 到 n - 1 之间的下标 i ，数字 abovei 所在的 行 必须在数字 belowi 所在行的上面。
对于所有 0 到 m - 1 之间的下标 i ，数字 lefti 所在的 列 必须在数字righti所在列的左边。
返回满足上述要求的 任意 矩阵。如果不存在答案，返回一个空的矩阵。
示例1:

输入：k = 3, rowConditions = [[1,2],[3,2]], colConditions = [[2,1],[3,2]]
输出：[[3,0,0],[0,0,1],[0,2,0]]
解释：上图为一个符合所有条件的矩阵。
行要求如下：
- 数字 1 在第 1 行，数字 2 在第 2 行，1 在 2 的上面。
- 数字 3 在第 0 行，数字 2 在第 2 行，3 在 2 的上面。
列要求如下：
- 数字 2 在第 1 列，数字 1 在第 2 列，2 在 1 的左边。
- 数字 3 在第 0 列，数字 2 在第 1 列，3 在 2 的左边。
注意，可能有多种正确的答案。
1
2
3
4
5
6
7
8
9
10

思路

起初用的暴力，但超时。后来看了y总的代码LeetCode 2392. 给定条件下构造矩阵，才想到用拓扑排序QAQ。看来最近得复习下基础了。
n个元素的拓扑排序问题：
题中所给的约束关系，比如a在b前面，与图论中a存在一条出边连接到b一致，通过构建邻接表和入度，可以得到符合条件的拓扑排序。显然，若答案不存在，则会产生环，那么拓扑排序所得到的数组个数将小于n。
在k*k矩阵中放入k个元素首先可以保证每行每列都只有一个元素，其余为0。而行条件得到的拓扑排序与列条件得到的拓扑排序是可以独立的，可以同时满足。通过行拓扑得到的数组，每个元素在矩阵中的的行位置就是它在该数组中的下标位置，同样地，该元素的列位置就是它在列拓扑排序数组的下标位置。

代码

class Solution {
public:
    int n;

    vector<int> topsort(vector<vector<int>> &es){
        vector<vector<int>> g(n + 1); // 构建邻接表
        vector<int> d(n + 1); // n个结点的入度

        for(auto &e : es){ // 图与入度的构建 
            int a = e[0], b = e[1];
            g[a].push_back(b);
            d[b] ++;
        }
        vector<int> res; // 拓扑排序
        queue<int> q; 
        for(int i = 1; i <= n; i ++ ){ // 首先放入度为0的结点
            if(!d[i]) q.push(i);
        }
        while(q.size()){ // 队列不空
            auto t = q.front();
            q.pop();
            res.push_back(t); // 队头结点放入答案数组
            // 删去该结点后更新度，若有0入度结点则入队
            for(int u : g[t]){ 
                if(-- d[u] == 0) q.push(u); 
            }
        }

        return res;
    }
	// 某个元素x通过拓扑排序数组来确定在矩阵中行或列的位置
    int get(vector<int> row, int x){ 
        for(int i = 0; i < n; i ++ ){
            if(row[i] == x) return i;
        }
        return -1;
    }

    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {
        n = k;
        auto row = topsort(rowConditions);
        auto col = topsort(colConditions);
        if(row.size() < n || col.size() < n) return {}; //存在环
        vector<vector<int>> res(n, vector<int>(n));
        for(int i = 1; i <= n; i ++ ){
            res[get(row, i)][get(col, i)] = i;
        }

        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

时间复杂度

设n为结点数，e为边数.
刚开始搜索0入度的结点使其入队时，复杂度为O(n)；每次弹出队头，更新其邻接点的入度(-- g[t])时，共执行了e次。因此时间复杂度为$O(n+e)$.