2024-04-06：用 go 语言，给你两个非负整数数组 rowSum 和 colSum，其中 rowSum[i] 是二维矩阵中第 i 行元素的和， colSum[j] 是第 j 列元素的和，换言之你

作者：福大大架构师每日一题

2024-04-06
北京
本文字数：1116 字
阅读完需：约 4 分钟

2024-04-06：用 go 语言，给你两个非负整数数组 rowSum 和 colSum，

其中 rowSum[i] 是二维矩阵中第 i 行元素的和，

colSum[j] 是第 j 列元素的和，换言之你不知道矩阵里的每个元素，

但是你知道每一行和每一列的和。

请找到大小为 rowSum.length x colSum.length 的任意非负整数矩阵。

且该矩阵满足 rowSum 和 colSum 的要求。

请你返回任意一个满足题目要求的二维矩阵，题目保证存在至少一个可行矩阵。

输入：rowSum = [3,8], colSum = [4,7]。

输出：[[3,0],[1,7]]。

答案 2024-04-06：

来自左程云。

灵捷3.5

大体步骤如下：

1.初始化一个大小为 rowSum.length x colSum.length 的二维矩阵 ans，用于存储最终的结果。

2.遍历 rowSum 数组，对于每个元素 rowSum[i]，继续遍历 colSum 数组，对于每个元素 colSum[j]：

将 ans[i][j]设为 rowSum[i]和 colSum[j]中的较小值，即 ans[i][j] = min(rowSum[i], colSum[j])。
更新 rowSum[i]和 colSum[j]，分别减去已经分配的值 ans[i][j]，即 rowSum[i] -= ans[i][j]，colSum[j] -= ans[i][j]。

3.返回 ans 作为结果矩阵。

总的时间复杂度：遍历 rowSum 和 colSum 数组需要 $O (n^{2})$ 的时间复杂度，其中 n 是 rowSum 和 colSum 的长度。因此，总的时间复杂度为 $O (n^{2})$ 。

总的额外空间复杂度：额外使用了一个二维矩阵 ans 来存储结果，其大小为 rowSum.length x colSum.length，因此总的额外空间复杂度为 $O (n^{2})$ 。

Go 完整代码如下：

package main
import (  "fmt")
func restoreMatrix(rowSum []int, colSum []int) [][]int {  n := len(rowSum)  m := len(colSum)  ans := make([][]int, n)  for i := 0; i < n; i++ {    ans[i] = make([]int, m)    for j := 0; j < m; j++ {      ans[i][j] = min(rowSum[i], colSum[j])      rowSum[i] -= ans[i][j]      colSum[j] -= ans[i][j]    }  }  return ans}
func min(a, b int) int {  if a < b {    return a  }  return b}
func main() {  rowSum := []int{3, 8}  colSum := []int{4, 7}  matrix := restoreMatrix(rowSum, colSum)  for _, row := range matrix {    fmt.Println(row)  }}

复制代码

Python 完整代码如下：

# -*-coding:utf-8-*-
def restoreMatrix(rowSum, colSum):    n = len(rowSum)    m = len(colSum)    ans = [[0] * m for _ in range(n)]    for i in range(n):        for j in range(m):            ans[i][j] = min(rowSum[i], colSum[j])            rowSum[i] -= ans[i][j]            colSum[j] -= ans[i][j]    return ans
def min(a, b):    if a < b:        return a    return b
rowSum = [3, 8]colSum = [4, 7]matrix = restoreMatrix(rowSum, colSum)for row in matrix:    print(row)