以下是 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{}。

 

Logo

中国智能体开发者社区,聚焦智能体与大模型开发,提供前沿资讯、实用工具链、开源项目及行业案例。通过技术沙龙、开发者大赛等活动,促进经验交流与协作,助力开发者快速构建创新智能应用。

更多推荐