文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目标题和出处标题给定行和列的和求可行矩阵出处1605. 给定行和列的和求可行矩阵难度5 级题目描述要求给定两个非负整数数组rowSum \texttt{rowSum}rowSum和colSum \texttt{colSum}colSum其中rowSum[i] \texttt{rowSum[i]}rowSum[i]是矩阵第i \texttt{i}i行元素的和colSum[j] \texttt{colSum[j]}colSum[j]是矩阵第j \texttt{j}j列元素的和。换言之不知道矩阵里的每个元素但是知道每一行与每一列的和。请找到大小为rowSum.length × colSum.length \texttt{rowSum.length} \times \texttt{colSum.length}rowSum.length×colSum.length的任意非负整数矩阵且该矩阵满足rowSum \texttt{rowSum}rowSum和colSum \texttt{colSum}colSum的要求。返回一个二维数组表示任意一个满足题目要求的矩阵。题目保证存在至少一个满足要求的矩阵。示例示例 1输入rowSum [3,8], colSum [4,7] \texttt{rowSum [3,8], colSum [4,7]}rowSum [3,8], colSum [4,7]输出[[3,0],[1,7]] \texttt{[[3,0],[1,7]]}[[3,0],[1,7]]解释第0 \texttt{0}0行3 0 3 rowSum[0] \texttt{3} \texttt{0} \texttt{3} \texttt{rowSum[0]}303rowSum[0]第1 \texttt{1}1行1 7 8 rowSum[1] \texttt{1} \texttt{7} \texttt{8} \texttt{rowSum[1]}178rowSum[1]第0 \texttt{0}0列3 1 4 colSum[0] \texttt{3} \texttt{1} \texttt{4} \texttt{colSum[0]}314colSum[0]第1 \texttt{1}1列0 7 7 colSum[1] \texttt{0} \texttt{7} \texttt{7} \texttt{colSum[1]}077colSum[1]行和列的和都满足题目要求且所有矩阵元素都是非负的。另一个可行的矩阵为[[1,2],[3,5]] \texttt{[[1,2],[3,5]]}[[1,2],[3,5]]。示例 2输入rowSum [5,7,10], colSum [8,6,8] \texttt{rowSum [5,7,10], colSum [8,6,8]}rowSum [5,7,10], colSum [8,6,8]输出[[0,5,0],[6,1,0],[2,0,8]] \texttt{[[0,5,0],[6,1,0],[2,0,8]]}[[0,5,0],[6,1,0],[2,0,8]]数据范围1 ≤ rowSum.length, colSum.length ≤ 500 \texttt{1} \le \texttt{rowSum.length, colSum.length} \le \texttt{500}1≤rowSum.length, colSum.length≤5000 ≤ rowSum[i], colSum[i] ≤ 10 8 \texttt{0} \le \texttt{rowSum[i], colSum[i]} \le \texttt{10}^\texttt{8}0≤rowSum[i], colSum[i]≤108sum(rowSum) sum(colSum) \texttt{sum(rowSum)} \texttt{sum(colSum)}sum(rowSum)sum(colSum)解法思路和算法用m mm和n nn分别表示数组rowSum \textit{rowSum}rowSum和数组colSum \textit{colSum}colSum的长度则需要构造一个m × n m \times nm×n的矩阵matrix \textit{matrix}matrix该矩阵的元素都是非负整数且满足每一行与每一列的和的要求。对于0 ≤ i m 0 \le i m0≤im和0 ≤ j n 0 \le j n0≤jn应满足matrix [ i ] [ j ] ≤ rowSum [ i ] \textit{matrix}[i][j] \le \textit{rowSum}[i]matrix[i][j]≤rowSum[i]且matrix [ i ] [ j ] ≤ colSum [ j ] \textit{matrix}[i][j] \le \textit{colSum}[j]matrix[i][j]≤colSum[j]否则矩阵的第i ii行或第j jj列的剩余元素之和将是负数矩阵中将存在负数不符合要求。如果matrix [ i ] [ j ] \textit{matrix}[i][j]matrix[i][j]的值过小则矩阵的第i ii行或第j jj列的剩余元素之和将过大导致其他行和列出现负数。为了确保得到符合要求的矩阵可以将矩阵的每个元素取不超过上界的最大值。依次遍历矩阵matrix \textit{matrix}matrix的每一个位置对于0 ≤ i m 0 \le i m0≤im和0 ≤ j n 0 \le j n0≤jn将matrix [ i ] [ j ] \textit{matrix}[i][j]matrix[i][j]的值设为min ⁡ ( rowSum [ i ] , colSum [ j ] ) \min(\textit{rowSum}[i], \textit{colSum}[j])min(rowSum[i],colSum[j])然后将rowSum [ i ] \textit{rowSum}[i]rowSum[i]和colSum [ j ] \textit{colSum}[j]colSum[j]都减去matrix [ i ] [ j ] \textit{matrix}[i][j]matrix[i][j]。遍历结束之后matrix \textit{matrix}matrix即为符合要求的矩阵。上述做法使用贪心策略贪心策略的正确性说明如下。由于计算矩阵matrix \textit{matrix}matrix中的每个元素时都将matrix [ i ] [ j ] \textit{matrix}[i][j]matrix[i][j]的值设为min ⁡ ( rowSum [ i ] , colSum [ j ] ) \min(\textit{rowSum}[i], \textit{colSum}[j])min(rowSum[i],colSum[j])然后将rowSum [ i ] \textit{rowSum}[i]rowSum[i]和colSum [ j ] \textit{colSum}[j]colSum[j]都减去matrix [ i ] [ j ] \textit{matrix}[i][j]matrix[i][j]因此在计算matrix [ i ] [ j ] \textit{matrix}[i][j]matrix[i][j]并更新rowSum [ i ] \textit{rowSum}[i]rowSum[i]和colSum [ j ] \textit{colSum}[j]colSum[j]之后matrix [ i ] [ j ] \textit{matrix}[i][j]matrix[i][j]、rowSum [ i ] \textit{rowSum}[i]rowSum[i]、colSum [ j ] \textit{colSum}[j]colSum[j]都一定非负且rowSum \textit{rowSum}rowSum的元素之和一定与colSum \textit{colSum}colSum的元素之和相等。将matrix \textit{matrix}matrix的第0 00行的所有元素都赋值之后必有rowSum [ 0 ] 0 \textit{rowSum}[0] 0rowSum[0]0。理由如下假设此时rowSum [ 0 ] 0 \textit{rowSum}[0] 0rowSum[0]0则数组colSum \textit{colSum}colSum的所有元素都变成0 00因此初始时数组colSum \textit{colSum}colSum的所有元素之和小于rowSum [ 0 ] \textit{rowSum}[0]rowSum[0]即待构造的矩阵的所有元素之和小于rowSum [ 0 ] \textit{rowSum}[0]rowSum[0]则待构造的矩阵从第1 11行到第m − 1 m - 1m−1行的所有元素之和是负数不符合题目的前提。将matrix \textit{matrix}matrix的第0 00行的所有元素都赋值之后矩阵剩余的部分为m − 1 m - 1m−1行和n nn列此时rowSum [ 0 ] 0 \textit{rowSum}[0] 0rowSum[0]0colSum \textit{colSum}colSum的每个元素分别为矩阵的剩余m − 1 m - 1m−1行元素中每一列的元素之和可以使用相同的方法依次构造矩阵的每一行。实现方面有一处可以优化。由于需要确保矩阵matrix \textit{matrix}matrix的每个元素都是非负整数因此每个元素的最小值为0 00遍历过程中对于当前行和列如果对应的rowSum \textit{rowSum}rowSum或colSum \textit{colSum}colSum的元素值为0 00则可以跳过当前行或列。代码classSolution{publicint[][]restoreMatrix(int[]rowSum,int[]colSum){intmrowSum.length,ncolSum.length;int[][]matrixnewint[m][n];introw0,col0;while(rowmcoln){intnumMath.min(rowSum[row],colSum[col]);matrix[row][col]num;rowSum[row]-num;colSum[col]-num;if(rowSum[row]0){row;}if(colSum[col]0){col;}}returnmatrix;}}复杂度分析时间复杂度O ( m × n ) O(m \times n)O(m×n)其中m mm和n nn分别是数组rowSum \textit{rowSum}rowSum和数组colSum \textit{colSum}colSum的长度。需要构造O ( m × n ) O(m \times n)O(m×n)的矩阵计算矩阵的每一个元素的时间都是O ( 1 ) O(1)O(1)。空间复杂度O ( 1 ) O(1)O(1)。注意返回值不计入空间复杂度。