1253. 重构 2 行二进制矩阵

LC每日一题，参考1253. 重构 2 行二进制矩阵，难度分1506。

题目

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

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

你需要利用 upper，lower 和 colsum 来重构这个矩阵，并以二维整数数组的形式返回它。
如果有多个不同的答案，那么任意一个都可以通过本题。
如果不存在符合要求的答案，就请返回一个空的二维数组。

解题思路

• 枚举贪心：考虑数据范围和题目要求,根据colsum的限制来枚举一列一列地填数,碰到 1 的时候看第一行和第二行的和哪个缺的多就填 1 。

class Solution {
    public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {
        int n = colsum.length;//n有10^5 暴力不行
        List<List<Integer>> ans = new ArrayList<>();
        //考虑一行 枚举列
        int[] u = new int[n],l = new int[n];
        int uSum = 0,lSum = 0;
        for(int i = 0; i < n ; i++) {
            int col = colsum[i];
            if(col == 2 || col == 0) {
                u[i] = l[i] = col/2;
                
            }else { //一个为零一个为1
                if(uSum < upper && lSum < lower) {
                    if(upper-uSum > lower-lSum) { //上面比较缺1
                        u[i] = 1;
                    }else {
                        l[i] = 1;
                    }
                }else if(uSum < upper){
                    u[i] = 1;
                }else if(lSum < lower) {
                    l[i] = 1;
                }else {
                    return ans;
                }
            }
            uSum += u[i];
            lSum += l[i];
        }
        if(uSum == upper && lSum == lower) {
            List<Integer> uList = new ArrayList<>(),lList = new ArrayList<>();
            for(int i : u) uList.add(i);
            for(int i : l) lList.add(i);
            ans.add(uList);
            ans.add(lList);
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：O(n)，一次遍历,n为colsum数组长度。
• 空间复杂度：O(n)，使用数组存储了结果加快了速度,也可以直接用队列O(1)。