DeepSeek LeetCode 2392.给定条件下构造矩阵 Go实现

以下是 LeetCode 2392「给定条件下构造矩阵」的 Go 语言实现，思路与之前相同：

1. 分别对行约束和列约束进行拓扑排序，得到行顺序和列顺序。
2. 若任一拓扑排序失败（存在环），则返回空矩阵。
3. 建立数字到行索引、列索引的映射。
4. 按映射填充 k x k 矩阵。

```go
func buildMatrix(k int, rowConditions [][]int, colConditions [][]int) [][]int {
// 拓扑排序辅助函数
topoSort := func(n int, edges [][]int) ([]int, bool) {
graph := make([][]int, n+1)
inDeg := make([]int, n+1)
for _, e := range edges {
u, v := e[0], e[1]
graph[u] = append(graph[u], v)
inDeg[v]++
}
queue := []int{}
for i := 1; i <= n; i++ {
if inDeg[i] == 0 {
queue = append(queue, i)
}
}
order := []int{}
for len(queue) > 0 {
u := queue[0]
queue = queue[1:]
order = append(order, u)
for _, v := range graph[u] {
inDeg[v]--
if inDeg[v] == 0 {
queue = append(queue, v)
}
}
}
if len(order) != n {
return nil, false
}
return order, true
}

rowOrder, ok := topoSort(k, rowConditions)
if !ok {
return [][]int{}
}
colOrder, ok := topoSort(k, colConditions)
if !ok {
return [][]int{}
}

// 建立数字 -> 行索引 / 列索引 的映射
rowPos := make([]int, k+1)
for i, num := range rowOrder {
rowPos[num] = i
}
colPos := make([]int, k+1)
for i, num := range colOrder {
colPos[num] = i
}

// 构造矩阵
mat := make([][]int, k)
for i := range mat {
mat[i] = make([]int, k)
}
for num := 1; num <= k; num++ {
r := rowPos[num]
c := colPos[num]
mat[r][c] = num
}
return mat
}
```

复杂度分析

· 时间复杂度：O(k + m)，其中 m 为 rowConditions 与 colConditions 的总边数。
· 空间复杂度：O(k + m)，用于存储图和入度数组。

注意事项

· 拓扑排序返回的顺序不唯一，任意合法顺序均可构造矩阵。
· 若行约束或列约束存在环，立即返回空 [][]int{}。