贪心 + 构造 $ O(n ^ 2) $
$matrix[i][j] =min(rowSum[i],colSum[j] )$
这样一定可以使得这个数字代表某一行或者某一列,非代表行or列也会减去,使得后面的(i, j)正确,
class Solution {
public:
vector<vector<int>> restoreMatrix(vector<int>& rowSum, vector<int>& colSum) {
int n = rowSum.size(), m = colSum.size();
vector<vector<int>> matrix(n, vector<int>(m, 0));
int i = 0, j = 0;
while (i < n && j < m) {
int v = min(rowSum[i], colSum[j]);
matrix[i][j] = v;
rowSum[i] -= v;
colSum[j] -= v;
if (rowSum[i] == 0) {
++i;
}
if (colSum[j] == 0) {
++j;
}
}
return matrix;
}
};
模拟 $ O(n ^ 2) $
笑死直接填入第一行,够了就往下挪
class Solution {
public:
inline vector<vector<int>> restoreMatrix(vector<int>& rowSum, vector<int>& colSum) {
int n = rowSum.size(), m = colSum.size();
vector<vector<int>> a(n, vector<int>(m, 0));
for (int i = 0; i < m; i ++)
a[0][i] = colSum[i];
for (int i = 0; i < n - 1; i ++)
{
int t = rowSum[i];
for (int j = 0; j < m; j ++) {
if (t <= a[i][j]) {
a[i + 1][j] = a[i][j] - t;
a[i][j] = t;
j ++;
while(j < m) {
a[i + 1][j] = a[i][j];
a[i][j] = 0;
j ++;
}
}else t -= a[i][j];
}
}
return a;
}
};