leetcode
leetcode 1451 ~ 1500
给定行和列的和求可行矩阵

给定行和列的和求可行矩阵

难度:

标签:

题目描述

代码结果

运行时间: 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]的值?这种选择对算法的正确性和效率有何影响?
选择`min(rowSum[i], colSum[j])`作为矩阵元素的值是为了确保不超过当前行和列的最大可能值,同时尽可能地满足行和列的总和要求。这种选择保证了算法的正确性,因为它避免了任何一个行或列的和被超出。从效率上讲,这种方法允许算法在遍历每个元素时立即决定其值,避免了需要回溯或重新调整已填充的值,从而提高了算法的执行效率。
🦆
在题解中,当`rowSum[i]`变为0后即刻增加i索引,移动到下一行,这种处理方式是否可能导致最后几列的`colSum[j]`无法精准匹配?
当`rowSum[i]`变为0后,增加i索引移动到下一行是基于当前行已经完全满足其需求的假设。这种做法理论上不会影响列的匹配,因为每一步操作都是基于行和列当前的需求来分配值。只要输入的行和列和是一致的,即总的行和等于总的列和,这种方法最终能够精确匹配所有行和列的需求。
🦆
题解中提到,如果`colSum[j]`为0,则立即增加j索引,移动到下一列。请问这种做法是否能保证所有行的和最终都能正确无误地匹配`rowSum`数组中的值?
是的,这种做法能够保证所有行的和最终匹配`rowSum`数组中的值。这是因为每次填充矩阵时都是根据当前行和列的需求来决定值的分配,只有当某一列的需求已经被完全满足,即`colSum[j]`为0时,才会移动到下一列。保证了不会有列和被提前耗尽而影响行和的匹配。
🦆
假设在某些情况下,`rowSum`或`colSum`中的一些数值极大,而其他数值极小,这种情况下贪心策略是否仍然适用?请解释为什么。
贪心策略在这种情况下仍然适用。贪心策略的核心在于每一步都尽可能满足当前行和列的最小需求,这样可以更平衡地分配矩阵中的值,避免任何一个行或列的需求未被满足。即使在极端情况下,例如某些行或列的值非常大或非常小,这种方法仍然能够确保每一步操作都是有效且合理的,从而最终满足所有行和列的总和要求。

相关问题