给定行和列的和求可行矩阵 图解题解
这道题到底在问什么
- 输入
- rowSum=[3,8], colSum=[4,7]
- 输出
- [[3,0],[1,7]]
- 输入
- rowSum=[5,7,10], colSum=[8,6,8]
- 输出
- [[5,0,0],[3,4,0],[0,2,8]]
最优解：一步一步想明白
- 3记住这个套路:每个格子填的是当前这一行余额和这一列余额里较小的那个,填完两边一起扣。为什么取较小值,因为填多了某一边就会超额变成负数。下面咱们从左上角开始,一格一格地填。
- 4橙格 = 待填,点号 = 还没决定这是一个 3 行 3 列的空矩阵,所有格子先用点号占位表示还没决定。右边面板上一排是每一行还差多少,现在是 5、7、10;下一排是每一列还差多少,现在是 8、6、8。注意这两排数字加起来都是 22,是相等的,这一点等会儿到最后一格会派上大用场。咱们从左上角第 0 行第 0 列开始填。
- 5取 min(5 , 8) = 5来到格子第 0 行第 0 列。这一行只差 5,这一列还差 8,这一行余额更少,取较小值 5。要是填得比 5 还多,这一行就超额了,所以最多填 5。
- 6行0 余 0 , 列0 余 3把 5 填进第 0 行第 0 列。填完之后,这一行余额从 5 变成 0,这一行后面的格子就只能填 0 了;这一列还差 3。
- 7取 min(0 , 6) = 0来到格子第 0 行第 1 列。这一行只差 0,这一列还差 6,这一行余额更少,取较小值 0。要是填得比 0 还多,这一行就超额了,所以最多填 0。
- 8行0 余 0 , 列1 余 6把 0 填进第 0 行第 1 列。填完之后,这一行余额从 0 变成 0,这一行后面的格子就只能填 0 了;这一列还差 6。
- 9取 min(0 , 8) = 0来到格子第 0 行第 2 列。这一行只差 0,这一列还差 8,这一行余额更少,取较小值 0。要是填得比 0 还多,这一行就超额了,所以最多填 0。
- 10行0 余 0 , 列2 余 8把 0 填进第 0 行第 2 列。填完之后,这一行余额从 0 变成 0,这一行后面的格子就只能填 0 了;这一列还差 8。
- 11行0 余额 = 0第 0 行填完了,内容是 5、0、0,加起来是 5,正好等于 rowSum 给的 5,这一行的余额已经归 0。接着填第 1 行。
- 12取 min(7 , 3) = 3来到格子第 1 行第 0 列。这一行还差 7,这一列只差 3,这一列余额更少,取较小值 3。填多了这一列就会超额,所以这一格填 3。
- 13行1 余 4 , 列0 余 0把 3 填进第 1 行第 0 列。填完之后,这一列余额从 3 变成 0,这一列后面的格子也只能填 0;这一行还差 4。
- 14取 min(4 , 6) = 4来到格子第 1 行第 1 列。这一行只差 4,这一列还差 6,这一行余额更少,取较小值 4。要是填得比 4 还多,这一行就超额了,所以最多填 4。
- 15行1 余 0 , 列1 余 2把 4 填进第 1 行第 1 列。填完之后,这一行余额从 4 变成 0,这一行后面的格子就只能填 0 了;这一列还差 2。
- 16取 min(0 , 8) = 0来到格子第 1 行第 2 列。这一行只差 0,这一列还差 8,这一行余额更少,取较小值 0。要是填得比 0 还多,这一行就超额了,所以最多填 0。
- 17行1 余 0 , 列2 余 8把 0 填进第 1 行第 2 列。填完之后,这一行余额从 0 变成 0,这一行后面的格子就只能填 0 了;这一列还差 8。
- 18行1 余额 = 0第 1 行填完了,内容是 3、4、0,加起来是 7,正好等于 rowSum 给的 7,这一行的余额已经归 0。接着填第 2 行。
- 19取 min(10 , 0) = 0来到格子第 2 行第 0 列。这一行还差 10,这一列只差 0,这一列余额更少,取较小值 0。这一列其实已经填够了,余额是 0,那这一格只能填 0。
- 20行2 余 10 , 列0 余 0把 0 填进第 2 行第 0 列。填完之后,这一列余额从 0 变成 0,这一列后面的格子也只能填 0;这一行还差 10。
- 21取 min(10 , 2) = 2来到格子第 2 行第 1 列。这一行还差 10,这一列只差 2,这一列余额更少,取较小值 2。填多了这一列就会超额,所以这一格填 2。
- 22行2 余 8 , 列1 余 0把 2 填进第 2 行第 1 列。填完之后,这一列余额从 2 变成 0,这一列后面的格子也只能填 0;这一行还差 8。
- 23取 min(8 , 8) = 8来到格子第 2 行第 2 列。这一行还差 8,这一列也还差 8,两边一样大,取较小值就是 8,准备把 8 填进去。
- 24行2 余 0 , 列2 余 0把 8 填进第 2 行第 2 列。填完之后,这一行余额归 0,这一列余额也归 0,两边同时填满了。
- 25行2 余额 = 0第 2 行填完了,内容是 0、2、8,加起来是 10,正好等于 rowSum 给的 10,这一行的余额已经归 0。所有格子都填完了,来看最终结果。
- 26行列的和全部对上整个矩阵填好了,是 5、0、0,3、4、0,0、2、8。验一下,每一行加起来是 5、7、10,跟 rowSum 完全一样;每一列加起来是 8、6、8,跟 colSum 也完全一样,所有数字都非负。最关键的是最右下角那一格,当时这一行还差 8、这一列也正好差 8,因为行总和等于列总和,前面每一步又都从两边扣掉相同的数,所以收尾这一格两边余额必然相等,稳稳填上 8 收官。
⚠️ 容易写错的地方
✗ 错：以为要解一大堆方程组才能反推矩阵
✓ 对：一遍贪心逐格填 min 就够了
行和列只约束各自的总和,自由度很大,根本不用解方程,行优先取较小值填一遍就得到一个合法解
✗ 错：把 min 写成 max,想着尽量多填
✓ 对：每格填的是行余额和列余额里较小的那个
填成较大值会让余额更小的那一边直接超额变成负数,破坏非负约束,必须取较小值
✗ 错：填完只扣了行余额,忘了同时扣列余额
✓ 对：填一个数要同时从对应行和对应列各减掉它
只扣一边会让另一边的余额虚高,后面的格子接着按错的余额填,整张表就全乱了
✗ 错：担心最后一格行余额和列余额对不上
✓ 对：题目保证行总和等于列总和,收尾必然相等
每步都从两边扣掉相同的数,两边余额的总和始终相等,填到最后一格时两个余额一定恰好相等
完整代码（Python / C++ / Java）
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 ansC++
#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;
}
}复杂度
时间
O(m·n)
m 是行数,n 是列数。整个算法就是一个双重循环把每个格子访问恰好一次,每个格子里做的取较小值和两次减法都是常数时间,所以总时间就是格子总数 m 乘 n
空间
O(1)
除了那张必须返回的 m 乘 n 答案矩阵之外,只用了 x 这一个临时变量和两个循环下标,没有额外随规模增长的辅助空间。返回矩阵是题目要求的输出,不计入额外空间,所以额外空间按峰值是常数 O(1)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 给定行和列的和求可行矩阵 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
怎么证明这个贪心一定能填出合法矩阵,不会卡住或出负数?+
分两点。第一,不会出负数:每格填的是行余额和列余额里较小的那个,它不超过任何一边的余额,减完两边都仍然非负。第二,最后一定填满:每填一格都让较小那边的余额归零,等价于划掉一行或一列;由于一开始行余额之和等于列余额之和,这个总和相等的关系每步都保持,所以填到任何阶段都不会出现一边还差很多另一边已经全 0 的死局,一路填到右下角行列余额同时归零。
填的顺序必须是行优先吗,换个顺序行不行?+
不必须。这个贪心对任意填格顺序都成立,核心只是维护每行余额、每列余额,每个格子填两者较小值再同减。换成列优先、或者按对角线顺序填,得到的矩阵可能长得不一样,但都是合法解,因为不出负数和总和相等这两条性质跟填的顺序无关。题目本来就允许返回任意一个可行矩阵。
这道题和运筹学或者图论里的什么模型有关系吗?+
它本质是运输问题里的一个经典构造。把每一行看成供给点、每一列看成需求点,要造一个运输方案让每个供给点发出的总量等于 rowSum、每个需求点收到的总量等于 colSum。我们用的逐格取较小值再消行消列,正是运输问题里求初始可行解的西北角法。所以这题既能用纯贪心直观理解,也能套上运输问题的框架来回答面试官的追问。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 给定行和列的和求可行矩阵 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。