1605. 给定行和列的和求可行矩阵 #
- 标签:贪心、数组、矩阵
- 难度:中等
题目大意 #
描述:给你两个非负整数数组 rowSum
和 colSum
,其中 rowSum[i]
是二维矩阵中第 i
行元素的和,colSum[j]
是第 j
列元素的和。换句话说,我们不知道矩阵里的每个元素,只知道每一行的和,以及每一列的和。
要求:找到并返回一个大小为 rowSum.length * colSum.length
的任意非负整数矩阵,且该矩阵满足 rowSum
和 colSum
的要求。
说明:
- 返回任意一个满足题目要求的二维矩阵即可,题目保证存在至少一个可行矩阵。
- $1 \le rowSum.length, colSum.length \le 500$。
- $0 \le rowSum[i], colSum[i] \le 10^8$。
- $sum(rows) == sum(columns)$。
示例:
- 示例 1:
|
|
解题思路 #
思路 1:贪心算法 #
题目要求找出一个满足要求的非负整数矩阵,矩阵中元素值可以为 0
。所以我们可以尽可能将大的值填入前面的行和列中,然后剩余位置用 0
补齐即可。具体做法如下:
- 使用二维数组
board
来保存答案,初始情况下,board
中元素全部赋值为0
。 - 遍历二维数组的每一行,每一列。当前位置下的值为当前行的和与当前列的和的较小值,即
board[row][col] = min(rowSum[row], colSum[col])
。 - 更新当前行的和,将当前行的和减去
board[row][col]
。 - 更新当前列的和,将当前列的和减去
board[row][col]
。 - 遍历完返回二维数组
board
。
思路 1:贪心算法代码 #
|
|