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

以下是 LeetCode 2392「给定条件下构造矩阵」的 Go 语言实现思路与之前相同1. 分别对行约束和列约束进行拓扑排序得到行顺序和列顺序。2. 若任一拓扑排序失败存在环则返回空矩阵。3. 建立数字到行索引、列索引的映射。4. 按映射填充 k x k 矩阵。gofunc buildMatrix(k int, rowConditions [][]int, colConditions [][]int) [][]int {// 拓扑排序辅助函数topoSort : func(n int, edges [][]int) ([]int, bool) {graph : make([][]int, n1)inDeg : make([]int, n1)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, k1)for i, num : range rowOrder {rowPos[num] i}colPos : make([]int, k1)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{}。