LeetCode 题解工作台
给定条件下构造矩阵
给你一个 正 整数 k ，同时给你： 一个大小为 n 的二维整数数组 rowConditions ，其中 rowConditions[i] = [above i , below i ] 和 一个大小为 m 的二维整数数组 colConditions ，其中 colConditions[i] = [l…
4
题型
5
代码语言
3
相关题
当前训练重点
困难 · 图
答案摘要
利用拓扑排序，找到一个合法的 `row` 序列和 `col` 序列，然后根据这两个序列构造出矩阵。 时间复杂度 。其中 和 分别为 `rowConditions` 和 `colConditions` 的长度，而 为题目中给定的正整数。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图 题型思路
题目描述
给你一个 正 整数 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 <= 4001 <= rowConditions.length, colConditions.length <= 104rowConditions[i].length == colConditions[i].length == 21 <= abovei, belowi, lefti, righti <= kabovei != belowilefti != righti
解题思路
方法一：拓扑排序
利用拓扑排序，找到一个合法的 row 序列和 col 序列，然后根据这两个序列构造出矩阵。
时间复杂度 。其中 和 分别为 rowConditions 和 colConditions 的长度，而 为题目中给定的正整数。
class Solution:
def buildMatrix(
self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]
) -> List[List[int]]:
def f(cond):
g = defaultdict(list)
indeg = [0] * (k + 1)
for a, b in cond:
g[a].append(b)
indeg[b] += 1
q = deque([i for i, v in enumerate(indeg[1:], 1) if v == 0])
res = []
while q:
for _ in range(len(q)):
i = q.popleft()
res.append(i)
for j in g[i]:
indeg[j] -= 1
if indeg[j] == 0:
q.append(j)
return None if len(res) != k else res
row = f(rowConditions)
col = f(colConditions)
if row is None or col is None:
return []
ans = [[0] * k for _ in range(k)]
m = [0] * (k + 1)
for i, v in enumerate(col):
m[v] = i
for i, v in enumerate(row):
ans[i][m[v]] = v
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(max(k\cdot k,n)) |
| 空间 | O(max(k\cdot k,n)) |
面试官常问的追问
外企场景- question_mark
Candidate efficiently applies topological sorting for graph problems.
- question_mark
Candidate detects and handles cyclic dependencies in the graph.
- question_mark
Candidate constructs a matrix efficiently by leveraging graph-based ordering.
常见陷阱
外企场景- error
Overlooking cyclic dependencies that make the matrix construction impossible.
- error
Incorrectly implementing the topological sorting algorithm.
- error
Misplacing numbers in the matrix after finding a valid topological order.
进阶变体
外企场景- arrow_right_alt
Implementing an algorithm for larger values of `k` (up to 400).
- arrow_right_alt
Handling a larger set of row and column constraints efficiently.
- arrow_right_alt
Modifying the problem to support partial matrix construction without fully satisfying constraints.