1 题目描述

给你一个 2 行 n 列的二进制数组：

• 矩阵是一个二进制矩阵，这意味着矩阵中的每个元素不是 0 就是 1。
• 第 0 行的元素之和为 upper。
• 第 1 行的元素之和为 lower。
• 第 i 列（从 0 开始编号）的元素之和为 colsum[i]，colsum 是一个长度为 n 的整数数组。

你需要利用 upper，lower 和 colsum 来重构这个矩阵，并以二维整数数组的形式返回它。

如果有多个不同的答案，那么任意一个都可以通过本题。

如果不存在符合要求的答案，就请返回一个空的二维数组。

2 示例

输入：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]] 也是正确答案。

提示

• 1 <= colsum.length <= 10^5
• 0 <= upper, lower <= colsum.length
• 0 <= colsum[i] <= 2

3 分析 - 贪心法

3.1 有解情况

• 若 colsum[i]=2colsum[i]=2，则 一定上下均为 1
• 若 colsum[i]=0colsum[i]=0，则 一定上下均为 0
• 若 colsum[i]=1colsum[i]=1，则 上下一个 1 一个 0

唯一需要讨论的只有 colsum[i]=1的情形
我们可以模拟：先upper为 1，再lower为 1

3.2 无解情况

3.2.1 （upper+lower） 不等于（∑colsum）

解决方案：一次循环，求∑colsum，与 upper+lower比较

3.2.2 等于了，但是不均，即行和不够或超

• 解决方案
  排除所有2 的项后再分配，观察此时 upper与 lower 是否为负值

算法

#include <stdlib.h>
#include <string.h>
int **reconstructMatrix(int upper, int lower, int *colsum, int colsumSize, int *returnSize, int **returnColumnSizes) {int **ret = malloc(2 * sizeof(int *));ret[0] = malloc(colsumSize * sizeof(int));memset(ret[0], 0, colsumSize * sizeof(int));ret[1] = malloc(colsumSize * sizeof(int));memset(ret[1], 0, colsumSize * sizeof(int));*returnColumnSizes = malloc(2 * sizeof(int *));int i;int sum = 0;int count = upper + lower;for (i = 0; i < colsumSize; i++) {sum += colsum[i];}for (i = 0; i < colsumSize; i++) {if (colsum[i] == 2) {ret[0][i] = 1;ret[1][i] = 1;upper--;lower--;continue;}}for (i = 0; i < colsumSize; i++) {if (colsum[i] == 1) {if (upper > 0) {ret[0][i] = 1;upper--;continue;}if (lower > 0) {ret[1][i] = 1;lower--;continue;}}}if (upper || lower || (sum != count)) {*returnSize = 0;(*returnColumnSizes)[0] = 0;(*returnColumnSizes)[1] = 0;return NULL;}// 确定返回数组的维度*returnSize = 2;(*returnColumnSizes)[0] = colsumSize;(*returnColumnSizes)[1] = colsumSize;return ret;
}

复杂度分析

时间复杂度：O(n)，空间复杂度：O(n)

参考

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reconstruct-a-2-row-binary-matrix