给定行和列的和求可行矩阵 图解题解

只知道每行每列的和，怎么倒推出矩阵

给两个非负整数数组 rowSum 和 colSum,rowSum[i] 是矩阵第 i 行之和，colSum[j] 是第 j 列之和。要造一个 rowSum.length 行、colSum.length 列的非负整数矩阵，让每行、每列的和都对上。题目保证有解，返回任意一个即可。题面例子 rowSum=[5,7,10]、colSum=[8,6,8]，答案之一是 [[5,0,0],[3,4,0],[0,2,8]]。

看到行列和就想列方程组，方程却不够用

3 行 3 列的矩阵有 9 个未知数，行和列却只给了 6 个方程，方程比未知数少、解本就不唯一，这也是题目允许『返回任意一个』的原因。真去列方程组反推没必要：行、列的和各自只约束自己那一维，自由度很大。只要一个合法解，顺着一格格填就能凑出来。

每格该填多大，取行列余额里的较小值

填每格前盯住两个数：这一行还差多少，记成行余额；这一列还差多少，记成列余额。这格填的数不能超过行余额、也不能超过列余额，否则对应的行或列就超标。两个上限取小的那个，就是这格能安全填下的最大值。所以每格填 min(行余额，列余额)。填成较大的那个，余额小的一边会被扣成负数，破坏非负约束。

填完一个数，行和列两笔账都要扣

定下这格填 x 后，把 x 从行余额和列余额里同时减掉。按行优先，从左上角起往右、填满一行再下一行，每到一格算 min、填进去、两边同减。哪边余额先归 0，那一行或那一列剩下的只能填 0。最常见的写错是只扣了行余额、忘了扣列余额：列余额虚高一截，后面接着按错的数填，整张表就全乱。

[5,7,10] 配 [8,6,8]，逐格填一遍

起手行余额 [5,7,10]、列余额 [8,6,8]。(0,0) min(5,8)=5，行余额转 [0,7,10]、列余额转 [3,6,8];(0,1) min(0,6)=0;(0,2) min(0,8)=0，第 0 行 [5,0,0]。

第 1 行：(1,0) min(7,3)=3，行余额转 [0,4,10]、列余额转 [0,6,8];(1,1) min(4,6)=4;(1,2) min(0,8)=0，得 [3,4,0]。第 2 行：(2,0) min(10,0)=0;(2,1) min(10,2)=2;(2,2) min(8,8)=8，两边同时归 0，得 [0,2,8]。拼起来是 [[5,0,0],[3,4,0],[0,2,8]]，每行和 5、7、10、每列和 8、6、8，正是题面两组数。

min 写成 max，整张表当场垮掉

最伤的错是把 min 写成 max、想多填：填成较大的那个，余额小的一边直接扣成负数，非负约束跟着破。另一个顾虑是怕填到右下角两边余额对不上；但题目保证行总和等于列总和，每格都从两边扣掉相同的数，两组余额总和始终相等，填到最后一格必然恰好相等、同时归 0。

复杂度上，双重循环把每个格子恰好访问一次，每格取较小值加两次减法都是常数，时间 O(m·n)；除答案矩阵外只多用一个临时变量，空间 O(1)。两个边界也想清：只有一格时直接填两边较小值；某行的和一开始就是 0，整行填 0。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:
        m, n = len(rowSum), len(colSum)
        ans = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                x = min(rowSum[i], colSum[j])
                ans[i][j] = x
                rowSum[i] -= x
                colSum[j] -= x
        return ans

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    vector<vector<int>> restoreMatrix(vector<int>& rowSum, vector<int>& colSum) {
        int m = rowSum.size(), n = colSum.size();
        vector<vector<int>> ans(m, vector<int>(n));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int x = min(rowSum[i], colSum[j]);
                ans[i][j] = x;
                rowSum[i] -= x;
                colSum[j] -= x;
            }
        }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public int[][] restoreMatrix(int[] rowSum, int[] colSum) {
        int m = rowSum.length;
        int n = colSum.length;
        int[][] ans = new int[m][n];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int x = Math.min(rowSum[i], colSum[j]);
                ans[i][j] = x;
                rowSum[i] -= x;
                colSum[j] -= x;
            }
        }
        return ans;
    }
}