1253. 重构 2 行二进制矩阵

---

给你一个 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]]

class Solution {
    public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {
    

    }
}    

分析与题解

---

由于 colsum 数组中元素只可能是 0, 1, 2 三种情况.

所以我一开始的想法非常简单,就是分以下几种情况分析.

• 如果 colsum[i] = 2, 那么就是 upperArray[i] = lowerArray[i] = 1 才能满足条件

• 如果 colsum[i] = 0, 那么就是 upperArray[i] = lowerArray[i] = 0 才能满足条件

• 如果 colsum[i] = 1, 这种情况就比较复杂了,又分为以下几种情况.

  • 先尝试 upperArray[i] = 1, 这种情况就是 upper > 0, 当这种情况满足时 upper--
  • 如果上面不满足,则尝试 lowerArray[i] = 1,这种情况也需要 lower > 0 , 当这种情况满足时 lower--
  • 当上面两种情况都不满足,则 upper < 0 && lower < 0 必然成立, 没法构建这样的二维数组,直接返回空数组即可.

• 当然了,在 colsum[i] = 2 时,需要同时 upper-- 和 lower--, 并且需要 先排除所有 colsum[i] = 2 的情况 , 这样可以排除 colsum[i] = 2 对 colsum[i] = 1 的干扰.

• 然后就需要一边构建 upperArray 和 lowerArray ,一边判断 upper 和 lower 是否满足条件.

思路是这样.整体暴力法代码如下所示.

class Solution {
    public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {
        // 暴力法
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        List<Integer> upperArray = new ArrayList<Integer>();
        List<Integer> lowerArray = new ArrayList<Integer>();
        int totalNumber = upper + lower;
        int colsumTotalNumber = 0;

        for (int i = 0; i < colsum.length; i++) {
            colsumTotalNumber += colsum[i];
            if (colsum[i] == 2) {
                // 如果元素为2,那么需要平均分配,分配完成之后就删除
                upperArray.add(i, 1);
                lowerArray.add(i, 1);
                upper -= 1;
                lower -= 1;
            } else {
                // 1 和 0 不做处理 直接添加
                upperArray.add(i, 0);
                lowerArray.add(i, 0);
            }
        }
        // 分配完成判断是否满足条件,不满足条件直接return
        if (colsumTotalNumber != totalNumber || upper < 0 || lower < 0) {
            return result;
        }
        for (int i = 0; i < colsum.length; i++) {
           if (colsum[i] == 1) {
                // 先分配第一个数组中
                if (upper > 0) {
                    // 更新元素
                    upperArray.remove(i);
                    upperArray.add(i, 1);
                    upper -= 1;
                } else if (lower > 0) {
                    // 更新元素
                    lowerArray.remove(i);
                    lowerArray.add(i, 1);
                    lower -= 1;
                } else {
                    // 当前 upper 和 lower 都为 0 分配满了,则直接不满足分配条件返回空数组
                    return result;
                }
            } else {
                // 0 不做处理 直接添加
            }
        }

        result.add(upperArray);
        result.add(lowerArray);
        return result;
    }
}

暴力法效率比较低,结果如下所示.