# LeetCode: 1253. 重构 2 行二进制矩阵¶

## 1、题目描述¶

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

输入：upper = 2, lower = 1, colsum = [1,1,1]



输入：upper = 2, lower = 3, colsum = [2,2,1,1]



输入：upper = 5, lower = 5, colsum = [2,1,2,0,1,0,1,2,0,1]



• $1 <= colsum.length <= 10^5$
• $0 <= upper, lower <= colsum.length$
• $0 <= colsum[i] <= 2$

## 2、解题思路¶

• 贪心法
• 首先将所有的和为2的找出来，然后上下两个数字这些位置都设置为1
• 然后将上面的剩余的1的数量进行补位，对应和的位置为1的
• 然后在用下面的剩余的1的数量进行补位，对应和的位置为1的
class Solution:
def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:
length = len(colsum)
first = [0] * length
second = [0] * length

for i in range(length):
if colsum[i] == 2:
upper -= 1
lower -= 1
first[i] = 1
second[i] = 1

if upper < 0 or lower < 0:
return []
pos = 0
while upper > 0 and pos < length:
if colsum[pos] == 1:
first[pos] = 1
upper -= 1
pos += 1
while lower > 0 and pos < length:
if colsum[pos] == 1:
second[pos] = 1
lower -= 1
pos += 1

if upper == 0 and lower == 0:
if pos >= length or all([x in [0, 2] for x in colsum[pos:]]):
return [first, second]

return []