贪心题目：给定行和列的和求可行矩阵

题目

标题和出处

标题：给定行和列的和求可行矩阵

出处：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]}3+0=3=rowSum[0]
第1 \texttt{1}1行：1 + 7 = 8 = rowSum[1] \texttt{1} + \texttt{7} = \texttt{8} = \texttt{rowSum[1]}1+7=8=rowSum[1]
第0 \texttt{0}0列：3 + 1 = 4 = colSum[0] \texttt{3} + \texttt{1} = \texttt{4} = \texttt{colSum[0]}3+1=4=colSum[0]
第1 \texttt{1}1列：0 + 7 = 7 = colSum[1] \texttt{0} + \texttt{7} = \texttt{7} = \texttt{colSum[1]}0+7=7=colSum[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≤500
• 0 ≤ rowSum[i], colSum[i] ≤ 10 8 \texttt{0} \le \texttt{rowSum[i], colSum[i]} \le \texttt{10}^\texttt{8}0≤rowSum[i], colSum[i]≤108
• sum(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≤i<m和0 ≤ j < n 0 \le j < n0≤j<n，应满足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≤i<m和0 ≤ j < n 0 \le j < n0≤j<n，将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即为符合要求的矩阵。

上述做法使用贪心策略，贪心策略的正确性说明如下。

1. 由于计算矩阵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的元素之和相等。

2. 将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行的所有元素之和是负数，不符合题目的前提。

3. 将matrix \textit{matrix}matrix的第0 00行的所有元素都赋值之后，矩阵剩余的部分为m − 1 m - 1m−1行和n nn列，此时rowSum [ 0 ] = 0 \textit{rowSum}[0] = 0rowSum[0]=0，colSum \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){intm=rowSum.length,n=colSum.length;int[][]matrix=newint[m][n];introw=0,col=0;while(row<m&&col<n){intnum=Math.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)。注意返回值不计入空间复杂度。