Medium

题目描述

给你两个非负整数数组 rowSum 和 colSum，其中 rowSum[i] 是二维矩阵中第 i 行元素的和，colSum[j] 是第 j 列元素的和。换言之，你不知道矩阵里的每个元素，但是你知道每一行和每一列的和。

请找到大小为 rowSum.length x colSum.length 的任意非负整数矩阵，且该矩阵满足 rowSum 和 colSum 的要求。

请返回任意一个满足题目要求的二维数组。题目保证存在至少一个有效的矩阵。

示例 1：

输入：rowSum = [3,8], colSum = [4,7]
输出：[[3,0],
      [1,7]]
解释：
第 0 行：3 + 0 = 3 == rowSum[0]
第 1 行：1 + 7 = 8 == rowSum[1]
第 0 列：3 + 1 = 4 == colSum[0]
第 1 列：0 + 7 = 7 == colSum[1]
行和列的和都满足题目要求，且所有矩阵元素都是非负的。
另一个可行的矩阵为：[[1,2],
                    [3,5]]

示例 2：

输入：rowSum = [5,7,10], colSum = [8,6,8]
输出：[[0,5,0],
      [6,1,0],
      [2,0,8]]

提示：

  • 1 <= rowSum.length, colSum.length <= 500
  • 0 <= rowSum[i], colSum[i] <= 10^8
  • sum(rowSum) == sum(colSum)

解题思路

这是一个经典的贪心算法问题。核心思路是每次选择当前行和列剩余和的最小值来填入矩阵。

贪心策略分析：

  1. 对于位置 (i, j)，我们需要在不超过 rowSum[i] 和 colSum[j] 的前提下，尽可能多地填入数字
  2. 最优选择是 min(rowSum[i], colSum[j])，这样可以最大化当前位置的贡献，同时不违反约束
  3. 填入数字后，相应地减少对应行和列的剩余和

算法步骤：

  1. 创建结果矩阵，初始化为全0
  2. 从左上角开始，按行遍历每个位置
  3. 对于位置 (i, j)，取 min(rowSum[i], colSum[j]) 作为该位置的值
  4. 更新剩余的行和与列和
  5. 继续处理下一个位置

这种贪心策略的正确性基于：每次选择最小值可以确保不会过早耗尽某一行或某一列的和，从而保证最终能够构造出满足所有约束的矩阵。

时间复杂度为 O(m×n)，空间复杂度为 O(1)（不计算结果矩阵）。

代码实现

class Solution {
public:
    vector<vector<int>> restoreMatrix(vector<int>& rowSum, vector<int>& colSum) {
        int m = rowSum.size(), n = colSum.size();
        vector<vector<int>> result(m, vector<int>(n, 0));
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int val = min(rowSum[i], colSum[j]);
                result[i][j] = val;
                rowSum[i] -= val;
                colSum[j] -= val;
            }
        }
        
        return result;
    }
};

class Solution:
    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:
        m, n = len(rowSum), len(colSum)
        result = [[0] * n for _ in range(m)]
        
        for i in range(m):
            for j in range(n):
                val = min(rowSum[i], colSum[j])
                result[i][j] = val
                rowSum[i] -= val
                colSum[j] -= val
        
        return result

public class Solution {
    public int[][] RestoreMatrix(int[] rowSum, int[] colSum) {
        int m = rowSum.Length, n = colSum.Length;
        int[][] result = new int[m][];
        for (int i = 0; i < m; i++) {
            result[i] = new int[n];
        }
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int val = Math.Min(rowSum[i], colSum[j]);
                result[i][j] = val;
                rowSum[i] -= val;
                colSum[j] -= val;
            }
        }
        
        return result;
    }
}

var restoreMatrix = function(rowSum, colSum) {
    const m = rowSum.length, n = colSum.length;
    const result = Array.from({length: m}, () => Array(n).fill(0));
    
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            const val = Math.min(rowSum[i], colSum[j]);
            result[i][j] = val;
            rowSum[i] -= val;
            colSum[j] -= val;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(m × n)
空间复杂度O(1)

其中 m 是行数，n 是列数。空间复杂度不计算输出结果矩阵的空间。

相关题目