题目名称

给你两个非负整数数组 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]]
解释:
第 0 行:3 + 0 = 3 == rowSum[0]
第 1 行:1 + 7 = 8 == rowSum[1]
第 0 列:3 + 1 = 4 == colSum[0]
第 1 列:0 + 7 = 7 == colSum[1]
行和列的和都满足题目要求,且所有矩阵元素都是非负的。
另一个可行的矩阵为:[[1,2],
[3,5]]

输入:rowSum = [5,7,10], colSum = [8,6,8]
输出:[[0,5,0],
[6,1,0],
[2,0,8]]

题解

首先声明一下,这个题我开始没想到思路,是根据leetcode 官方题解来做的

官方题解采用了贪心算法。

保证生成的二维数组中,当前位置,是所在 i 行,j 列中的最大值,这样没有遍历到的地方就是不需要分配值的地方,也就是 0

思很清奇,可惜脑子有点转不过来,没有想到

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
var restoreMatrix = function(rowSum, colSum) {
const n = rowSum.length, m = colSum.length;
const matrix = new Array(n).fill(0).map(() => new Array(m).fill(0));
let i = 0, j = 0;
while (i < n && j < m) {
const v = Math.min(rowSum[i], colSum[j]);
console.log(v, i, j)
matrix[i][j] = v;
rowSum[i] -= v;
colSum[j] -= v;
if (rowSum[i] === 0) {
++i;
}
if (colSum[j] === 0) {
++j;
}
}
return matrix;

};

// console.log(restoreMatrix([3,8], [4,7]), "[[3,0],[1,7]]")
console.log(restoreMatrix([5,7,10], [8,6,8]), "[[0,5,0],[6,1,0],[2,0,8]]")