LC 1253. 重构 2 行二进制矩阵

题目描述

这是 LeetCode 上的 1253. 重构 2 行二进制矩阵 ，难度为 中等。

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

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

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

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

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

示例 1：

1
2
3
4
5
输入：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：
1
2
3
输入：upper = 2, lower = 3, colsum = [2,2,1,1]

输出：[]

示例 3：
1
2
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^5$
  • $0 <= upper, lower <= colsum.length$
  • $0 <= colsum[i] <= 2$

贪心 + 构造

创建数组 a 和 b 分别代表目标二进制矩阵的第 0 行和第 1 行。

从前往后处理 colsum，复用 upper 和 lower 分别代表两行剩余 $1$ 的个数。

根据当前的 $colsum[i]$ 进行分情况讨论：

  • 若 $colsum[i] = 0$，只有一种情况，当前位置两行均为 $0$
  • 若 $colsum[i] = 2$，只有一种情况，当前位置两行均为 $1$
  • 若 $colsum[i] = 1$，选剩余 1 个数较大的行，填入 $1$，另外行则填入 $0$

若处理完 colsum 后，两行剩余 $1$ 个数恰好均为 $0$，说明构造出了合法方案。

容易证明：不存在某个决策回合中，必须先填入剩余个数少的一方，才能顺利构造。

可用反证法进行证明，若存在某个回合必须填入剩余个数少的一方（假设该回合上填 1 下填 0），必然能够找到同为 $colsum[j] = 1$ 的回合进行交换，同时不影响合法性（上下行的总和不变，同时 $colsum[i] = colsum[j] = 1$）。

Java 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {
        int n = colsum.length;
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> a = new ArrayList<>(), b = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int m = colsum[i];
            if (m == 0) {
                a.add(0); b.add(0);
            } else if (m == 2) {
                upper--; lower--;
                a.add(1); b.add(1);
            } else {
                if (upper >= lower) {
                    upper--;
                    a.add(1); b.add(0);
                } else {
                    lower--;
                    a.add(0); b.add(1);
                }
            }
        }
        if (upper == 0 && lower == 0) {
            ans.add(a); ans.add(b);
        }
        return ans;
    }
}

C++ 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& colsum) {
        int n = colsum.size();
        vector<vector<int>> ans;
        vector<int> a, b;
        for (int i = 0; i < n; i++) {
            int m = colsum[i];
            if (m == 0) {
                a.push_back(0); b.push_back(0);
            } else if (m == 2) {
                upper--; lower--;
                a.push_back(1); b.push_back(1);
            } else {
                if (upper >= lower) {
                    upper--;
                    a.push_back(1); b.push_back(0);
                } else {
                    lower--;
                    a.push_back(0); b.push_back(1);
                }
            }
        }
        if (upper == 0 && lower == 0) {
            ans.push_back(a); ans.push_back(b);
        }
        return ans;
    }
};

Python 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:
        n = len(colsum)
        ans = []
        a, b = [], []
        for i in range(n):
            m = colsum[i]
            if m == 0:
                a.append(0)
                b.append(0)
            elif m == 2:
                upper, lower = upper - 1, lower - 1
                a.append(1)
                b.append(1)
            else:
                a.append(1 if upper >= lower else 0)
                b.append(0 if upper >= lower else 1)
                if upper >= lower: upper -= 1
                else: lower -= 1
        if upper == lower == 0:
            ans.append(a)
            ans.append(b)
        return ans

TypeScript 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function reconstructMatrix(upper: number, lower: number, colsum: number[]): number[][] {
    const n = colsum.length;
    let ans: number[][] = [];
    let a: number[] = [], b: number[] = [];
    for (let i = 0; i < n; i++) {
        const m = colsum[i];
        if (m === 0) {
            a.push(0); b.push(0);
        } else if (m === 2) {
            upper--; lower--;
            a.push(1); b.push(1);
        } else {
            if (upper >= lower) {
                upper--;
                a.push(1); b.push(0);
            } else {
                lower--;
                a.push(0); b.push(1);
            }
        }
    }
    if (upper === 0 && lower === 0) {
        ans.push(a); ans.push(b);
    }
    return ans;
};

  • 时间复杂度：$O(C \times n)$，其中 $C = 2$ 代表行数
  • 空间复杂度：$O(C \times n)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1253 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。