2392-给定条件下构造矩阵

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:25 2023-09-13 16:06:25 Updated    

给你一个 正 整数 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 的左边。
注意，可能有多种正确的答案。

示例 2：

**输入：** k = 3, rowConditions = [[1,2],[2,3],[3,1],[2,3]], colConditions = [[2,1]]
**输出：** []
**解释：** 由前两个条件可以得到 3 在 1 的下面，但第三个条件是 3 在 1 的上面。
没有符合条件的矩阵存在，所以我们返回空矩阵。

提示：

  • 2 <= k <= 400
  • 1 <= rowConditions.length, colConditions.length <= 104
  • rowConditions[i].length == colConditions[i].length == 2
  • 1 <= abovei, belowi, lefti, righti <= k
  • abovei != belowi
  • lefti != righti

视频讲解 已出炉，包括本题拓扑排序的原理，欢迎素质三连，在评论区分享你对这场周赛的看法~

提示 1

数字之间的约束只发生在行与行、列于列，而行与列之间没有直接约束。

因此我们可以分别处理行与列中数字的相对顺序，如何求出这个相对顺序呢？

提示 2

拓扑排序。

提示 3

对于 rowConditions，我们可以从 above}_i 向 below}_i 连一条有向边，得到一张有向图。在这张图上跑拓扑排序，得到的拓扑序就是行与行中数字的相对顺序，这样我们就知道了每一行要填哪个数字。如果得到的拓扑序长度不足 k，说明图中有环，无法构造，答案不存在。

对 colConditions 也执行上述过程，得到每一列要填哪个数字，进而得到每个数字要填到哪一列中，这样我们就知道每一行的数字要填到哪一列了。

答疑

Q：下面拓扑排序的代码，是怎么处理孤立点（没有连边的点，对于本题来说是没有受到任何约束的数字）的？
A：孤立点入度为 0，在一开始就入队了，进而在后续的循环中加到了拓扑序中。

复杂度分析

  • 时间复杂度：O(k^2+n+m)，其中 n 为 rowConditions 的长度， m 为 colConditions 的长度。
  • 空间复杂度：O(k+n+m)。忽略返回值占用的空间复杂度。

相关题目

[sol1-Python3]
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
class Solution:
    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:
        def topo_sort(edges: List[List[int]]) -> List[int]:
            g = [[] for _ in range(k)]
            in_deg = [0] * k
            for x, y in edges:
                g[x - 1].append(y - 1)  # 顶点编号从 0 开始，方便计算
                in_deg[y - 1] += 1
            order = []
            q = deque(i for i, d in enumerate(in_deg) if d == 0)
            while q:
                x = q.popleft()
                order.append(x)
                for y in g[x]:
                    in_deg[y] -= 1
                    if in_deg[y] == 0:
                        q.append(y)
            return order if len(order) == k else None

        if (row := topo_sort(rowConditions)) is None or (col := topo_sort(colConditions)) is None:
            return []
        pos = {x: i for i, x in enumerate(col)}
        ans = [[0] * k for _ in range(k)]
        for i, x in enumerate(row):
            ans[i][pos[x]] = x + 1
        return ans
[sol1-Java]
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
class Solution {
    int[] topoSort(int k, int[][] edges) {
        List<Integer>[] g = new ArrayList[k];
        Arrays.setAll(g, e -> new ArrayList<>());
        var inDeg = new int[k];
        for (var e : edges) {
            int x = e[0] - 1, y = e[1] - 1; // 顶点编号从 0 开始，方便计算
            g[x].add(y);
            ++inDeg[y];
        }

        var order = new ArrayList<Integer>();
        var q = new ArrayDeque<Integer>();
        for (var i = 0; i < k; ++i)
            if (inDeg[i] == 0) q.push(i);
        while (!q.isEmpty()) {
            var x = q.pop();
            order.add(x);
            for (var y : g[x])
                if (--inDeg[y] == 0) q.push(y);
        }
        return order.stream().mapToInt(x -> x).toArray();
    }

    public int[][] buildMatrix(int k, int[][] rowConditions, int[][] colConditions) {
        int[] row = topoSort(k, rowConditions), col = topoSort(k, colConditions);
        if (row.length < k || col.length < k) return new int[][]{};
        var pos = new int[k];
        for (var i = 0; i < k; ++i)
            pos[col[i]] = i;
        var ans = new int[k][k];
        for (var i = 0; i < k; ++i)
            ans[i][pos[row[i]]] = row[i] + 1;
        return ans;
    }
}
[sol1-C++]
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
class Solution {
    vector<int> topo_sort(int k, vector<vector<int>> &edges) {
        vector<vector<int>> g(k);
        vector<int> in_deg(k);
        for (auto &e : edges) {
            int x = e[0] - 1, y = e[1] - 1; // 顶点编号从 0 开始，方便计算
            g[x].push_back(y);
            ++in_deg[y];
        }

        vector<int> order;
        queue<int> q;
        for (int i = 0; i < k; ++i)
            if (in_deg[i] == 0)
                q.push(i);
        while (!q.empty()) {
            int x = q.front();
            q.pop();
            order.push_back(x);
            for (int y : g[x])
                if (--in_deg[y] == 0)
                    q.push(y);
        }
        return order;
    }

public:
    vector<vector<int>> buildMatrix(int k, vector<vector<int>> &rowConditions, vector<vector<int>> &colConditions) {
        auto row = topo_sort(k, rowConditions), col = topo_sort(k, colConditions);
        if (row.size() < k || col.size() < k) return {};
        vector<int> pos(k);
        for (int i = 0; i < k; ++i)
            pos[col[i]] = i;
        vector<vector<int>> ans(k, vector<int>(k));
        for (int i = 0; i < k; ++i)
            ans[i][pos[row[i]]] = row[i] + 1;
        return ans;
    }
};
[sol1-Go]
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
func topoSort(k int, edges [][]int) []int {
	g := make([][]int, k)
	inDeg := make([]int, k)
	for _, e := range edges {
		x, y := e[0]-1, e[1]-1 // 顶点编号从 0 开始，方便计算
		g[x] = append(g[x], y)
		inDeg[y]++
	}
	q := make([]int, 0, k)
	orders := q // 复用队列作为拓扑序
	for i, d := range inDeg {
		if d == 0 {
			q = append(q, i)
		}
	}
	for len(q) > 0 {
		x := q[0]
		q = q[1:]
		for _, y := range g[x] {
			if inDeg[y]--; inDeg[y] == 0 {
				q = append(q, y)
			}
		}
	}
	if cap(q) > 0 {
		return nil
	}
	return orders[:k]
}

func buildMatrix(k int, rowConditions, colConditions [][]int) [][]int {
	row := topoSort(k, rowConditions)
	col := topoSort(k, colConditions)
	if row == nil || col == nil {
		return nil
	}
	pos := make([]int, k)
	for i, v := range col {
		pos[v] = i
	}
	ans := make([][]int, k)
	for i, x := range row {
		ans[i] = make([]int, k)
		ans[i][pos[x]] = x + 1
	}
	return ans
}

思考题

如果问题变成一个三维的立方格，再添加一个 z 轴上的数字约束，要怎么做？

 Comments
On this page
2392-给定条件下构造矩阵