给你一个 2 行 n 列的二进制数组：
- 矩阵是一个二进制矩阵，这意味着矩阵中的每个元素不是
0就是1。 - 第
0行的元素之和为upper。 - 第
1行的元素之和为lower。 - 第
i列（从0开始编号）的元素之和为colsum[i]，colsum是一个长度为n的整数数组。
你需要利用 upper，lower 和 colsum 来重构这个矩阵，并以二维整数数组的形式返回它。
如果有多个不同的答案，那么任意一个都可以通过本题。
如果不存在符合要求的答案，就请返回一个空的二维数组。
示例 1：
输入：upper = 2, lower = 1, colsum = [1,1,1]
输出：[[1,1,0],[0,0,1]]
解释：[[1,0,1],[0,1,0]] 和 [[0,1,1],[1,0,0]] 也是正确答案。
示例 2：
输入：upper = 2, lower = 3, colsum = [2,2,1,1]
输出：[]
示例 3：
输入：upper = 5, lower = 5, colsum = [2,1,2,0,1,0,1,2,0,1]
输出：[[1,1,1,0,1,0,0,1,0,0],[1,0,1,0,0,0,1,1,0,1]]
提示：
1 <= colsum.length <= 10^50 <= upper, lower <= colsum.length0 <= colsum[i] <= 2
解法 贪心
我们要求得任意一个 2 2 2 行 n n n 列的二进制数组（其中行和列的序号从 0 0 0 开始），满足数组中的每一个元素不是 0 0 0 就是 1 1 1 ，并且第 0 0 0 行的元素和为 upper \textit{upper} upper ，第 1 1 1 行的元素和为 lower \textit{lower} lower ，第 i i i 列的元素之和为 c o l s u m [ i ] colsum[i] colsum[i] ，若不存在直接返回一个空的二维数组即可。
记 s u m sum sum 为数组 c o l s u m colsum colsum 的元素和， t w o two two 为数组 c o l s u m colsum colsum 中 2 2 2 的个数。明显当 s u m ≠ u p p e r + l o w e r sum≠upper+lower sum=upper+lower 时，一定不存在满足题意的矩阵。然后当第 i i i 列 c o l s u m [ i ] = 2 colsum[i]=2 colsum[i]=2 时，第 i i i 列的两个元素只能都为 1 1 1 。那么如果 two > min { upper , lower } \textit{two} > \min\{\textit{upper}, \textit{lower}\} two>min{upper,lower} 时，此时同样不存在满足题意的矩阵。
否则，一定可以通过下述的方案，构造一个符合题目要求的矩阵。设结果矩阵为 ans [ 2 ] [ n ] \textit{ans}[2][n] ans[2][n] 。当第 i i i 列 c o l s u m [ i ] colsum[i] colsum[i] 等于 0 0 0 或者 2 2 2 时只有一种情况：
- c o l s u m [ i ] = 0 colsum[i]=0 colsum[i]=0 时： a n s [ 0 ] [ i ] = a n s [ 1 ] [ i ] = 0 ans[0][i]=ans[1][i]=0 ans[0][i]=ans[1][i]=0 。
- c o l s u m [ i ] = 2 colsum[i]=2 colsum[i]=2 时： ans [ 0 ] [ i ] = ans [ 1 ] [ i ] = 1 \textit{ans}[0][i] = \textit{ans}[1][i] = 1 ans[0][i]=ans[1][i]=1 。
所以，现在只关注 c o l s u m [ i ] = 1 colsum[i]=1 colsum[i]=1 的情况。首先将初始的 upper \textit{upper} upper 和 lower \textit{lower} lower 减去数组 c o l s u m colsum colsum 中 2 2 2 的个数 t w o two two（），那么现在 u p p e r + l o w e r upper+lower upper+lower 为数组 c o l s u m colsum colsum 中 1 1 1 的个数。那么从左到右遍历 c o l s u m colsum colsum 中的每一列，若第 i i i 列 c o l s u m [ i ] colsum[i] colsum[i] 等于 1 1 1 ：
- 若 u p p e r > 0 upper>0 upper>0 ，则我们在该列的第一行放置 1 1 1 ，第二行放置 0 0 0 ： a n s [ 0 ] [ i ] = 1 ans[0][i]=1 ans[0][i]=1， a n s [ 1 ] [ i ] = 0 ans[1][i]=0 ans[1][i]=0 ，并且 upper \textit{upper} upper 减一。
- 否则在该列的第一行放置 0 0 0 ，第二行放置 1 1 1 ： a n s [ 0 ] [ i ] = 0 ans[0][i]=0 ans[0][i]=0 ， ans [ 1 ] [ i ] = 1 \textit{ans}[1][i] = 1 ans[1][i]=1 。
当遍历完成后，就得到了符合题目要求的矩阵 a n s [ 2 ] [ n ] ans[2][n] ans[2][n] 。
现在给出该方案的正确性证明：从上述的构造过程可得，整个数组中除了 1 1 1 就 0 0 0 ，每一列中 1 1 1 的个数完全符合数组 c o l s u m colsum colsum 描述，且在第一行中我们共放置了 u p p e r upper upper 个 1 1 1 ，第二行共放置了 lower \textit{lower} lower 个 1 1 1 。因此这样构造的矩阵 a n s [ 2 ] [ n ] ans[2][n] ans[2][n] 为满足题意的二进制矩阵，正确性得证。
下面是我写的先贪心处理 2 2 2 的情况的代码：
class Solution {
public:
vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& colsum) {
int n = colsum.size();
vector<vector<int>> ans(2, vector<int>(n));
for (int j = 0; j < n; ++j) {
if (colsum[j] == 2) {
if (!upper || !lower) return {}; // 不够组成列
ans[0][j] = ans[1][j] = 1;
--upper, --lower;
}
}
for (int j = 0; j < n; ++j) {
if (colsum[j] == 1) {
if (!upper && !lower) return {}; // 不够组成列
if (upper) ans[0][j] = 1, --upper;
else ans[1][j] = 1, --lower;
}
}
if (!lower && !upper) return ans;
return {}; // 不够组成列
}
};
下面是先检查 c o l s u m colsum colsum 是否有解的代码：
class Solution {
public:
vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& colsum) {
int n = colsum.size();
vector<vector<int>> ans(2, vector<int>(n));
int sum = 0, two = 0; // two为colsum中2的个数
for (int j = 0; j < n; ++j) {
if (colsum[j] == 2) ++two;
sum += colsum[j];
}
if (sum != upper + lower || min(upper, lower) < two) return {};
upper -= two, lower -= two; // 相当于先处理2的情况
for (int j = 0; j < n; ++j) {
if (colsum[j] == 2) ans[0][j] = ans[1][j] = 1;
else if (colsum[j] == 1) {
if (upper) ans[0][j] = 1, --upper;
else ans[1][j] = 1;
}
}
return ans;
}
};
复杂度分析：
- 时间复杂度： O ( n ) O(n) O(n) ，其中 n n n 为数组 c o l s u m colsum colsum 的长度。
- 空间复杂度： O ( 1 ) O(1) O(1) ，仅使用常量空间。返回的结果数组不计入空间开销。