题目描述
这是 LeetCode 上的 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]]
|
提示:
- $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 原题链接和其他优选题解。