LC.P1253[重构2行二进制矩阵]

方法一:贪心

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
class Solution {
public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {
List<Integer> first = new ArrayList<>(), second = new ArrayList<>();
for (int sum : colsum) {
int a = 0, b = 0;
if (sum == 2) {
a = 1;
b = 1;
--upper;
--lower;
} else if (sum == 1) {
if (upper >= lower) {
a = 1;
--upper;
} else {
b = 1;
--lower;
}
}
if (upper < 0 || lower < 0) break;
first.add(a);
second.add(b);
}
return upper == 0 && lower == 0 ? List.of(first, second) : new ArrayList<>();
}
}
  • 时间复杂度:$O(n)$
  • 空间复杂度:$O(1)$