重构 2 行二进制矩阵【LC1253】
给你一个 2 行 n 列的二进制数组：
- 矩阵是一个二进制矩阵，这意味着矩阵中的每个元素不是
0就是1。 - 第
0行的元素之和为upper。 - 第
1行的元素之和为lower。 - 第
i列（从0开始编号）的元素之和为colsum[i]，colsum是一个长度为n的整数数组。
你需要利用 upper，lower 和 colsum 来重构这个矩阵，并以二维整数数组的形式返回它。
如果有多个不同的答案，那么任意一个都可以通过本题。
如果不存在符合要求的答案，就请返回一个空的二维数组。
思路
如果colsum中某个位置为2，那么两行中该位置都为1；如果某个位置为1，那么设置任意一行为1，另一行为0。因此可以先将一定是1的位置赋值为1，并计算需要赋值为1的位置和 upper、lower中剩余的数目是否相等，如果不相等，那么表示不可构造。否则，我们可以构造出该数组，由于只需要返回一个可能的答案，那么先将upper赋值为1，再将lower赋值为1
实现
class Solution { public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) { List<List<Integer>> res = new ArrayList<>(); int n = colsum.length; int[][] cur = new int[n][2]; int count1 = 0; for (int i = 0; i < n; i++){ if (colsum[i] == 2){ cur[i][0] = 1; cur[i][1] = 1; upper -= 1; lower -= 1; colsum[i] = 0; }else if (colsum[i] == 1){ count1++; } } if (upper < 0 || lower < 0 || upper + lower != count1){ return res; } for (int i = 0; i < n; i++){ if (colsum[i] == 1){ if (upper > 0){ cur[i][0] = 1; upper--; }else{ cur[i][1] = 1; lower--; } } } List<Integer> u = new ArrayList<>(); List<Integer> l = new ArrayList<>(); for (int i = 0; i < n; i++){ u.add(cur[i][0]); l.add(cur[i][1]); } res.add(u); res.add(l); return res; } }
复杂度
- 时间复杂度：O ( n l o g n )
- 空间复杂度：O(n)
