给定行和列的和求可行矩阵
难度:
标签:
题目描述
代码结果
运行时间: 43 ms, 内存: 20.3 MB
/*
* Solution Idea using Java Streams:
* The core idea remains the same: fill the matrix with the minimum possible values.
* However, this implementation will use Java Streams where possible for iteration.
*/
import java.util.Arrays;
public class Solution {
public int[][] restoreMatrix(int[] rowSum, int[] colSum) {
int rows = rowSum.length;
int cols = colSum.length;
int[][] matrix = new int[rows][cols];
Arrays.stream(matrix).forEach(row -> Arrays.fill(row, 0));
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
int minValue = Math.min(rowSum[i], colSum[j]);
matrix[i][j] = minValue;
rowSum[i] -= minValue;
colSum[j] -= minValue;
}
}
return matrix;
}
}
解释
方法:
题解的核心思路是贪心算法。对于每个矩阵元素 matrix[i][j],我们选择 rowSum[i] 和 colSum[j] 中较小的一个值作为其值,然后相应地减少 rowSum[i] 和 colSum[j]。这样确保了不会超过任一行或列的总和。对于每个元素的选取,都是尽可能地满足当前行和列的需求,直到填满整个矩阵。
时间复杂度:
O(n*m)
空间复杂度:
O(n*m)
代码细节讲解
🦆
为什么选择`min(rowSum[i], colSum[j])`作为矩阵元素matrix[i][j]的值?这种选择对算法的正确性和效率有何影响?
▷🦆
在题解中,当`rowSum[i]`变为0后即刻增加i索引,移动到下一行,这种处理方式是否可能导致最后几列的`colSum[j]`无法精准匹配?
▷🦆
题解中提到,如果`colSum[j]`为0,则立即增加j索引,移动到下一列。请问这种做法是否能保证所有行的和最终都能正确无误地匹配`rowSum`数组中的值?
▷🦆
假设在某些情况下,`rowSum`或`colSum`中的一些数值极大,而其他数值极小,这种情况下贪心策略是否仍然适用?请解释为什么。
▷