重构 2 行二进制矩阵

难度: Medium

给你一个 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

Submission

运行时间: 57 ms

内存: 21.6 MB

class Solution:
    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:
        if sum(colsum) != upper + lower:
            return []
        if sum(1 for c in colsum if c == 2) > min(upper,lower):
            return []
        up = [1 if c == 2 else 0 for c in colsum]
        u1 = sum(up)
        low = [0] * len(colsum)
        for i,c in enumerate(colsum):
            if u1 < upper and c == 1:
                up[i] = 1
                u1 += 1
            low[i] = c - up[i]
        return [up, low]

Explain

该题解的思路基于有效地分配'1'到两行上，以满足每列的和（colsum）以及每行的和（upper和lower）。首先，如果colsum的总和不等于upper和lower的和，那么无法构建所需的矩阵，因此直接返回空数组。接着检查colsum中值为2的个数是否超过upper和lower中的最小值，如果超过，则同样返回空数组，因为无法满足列和的要求。然后，初始化两个数组up和low，分别表示最终矩阵的第一行和第二行。先遍历colsum，将所有值为2的情况分配到两行，因为colsum为2意味着这一列的两个位置必须都是1。接着，再次遍历colsum，针对值为1的情况，尽量分配到第一行（up），直到第一行的和达到upper。最后，根据colsum减去up的值来确定low的值。这样可以构建满足条件的矩阵。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:
        # 检查colsum总和是否等于upper加lower之和
        if sum(colsum) != upper + lower:
            return []
        # 检查colsum中值为2的元素个数是否超过upper和lower的最小值
        if sum(1 for c in colsum if c == 2) > min(upper,lower):
            return []
        # 初始化第一行，将colsum为2的位置设置为1
        up = [1 if c == 2 else 0 for c in colsum]
        # 计算初始化后第一行1的个数
        u1 = sum(up)
        # 初始化第二行
        low = [0] * len(colsum)
        # 遍历colsum，将剩余的1尽量分配到第一行直到达到upper限制
        for i,c in enumerate(colsum):
            if u1 < upper and c == 1:
                up[i] = 1
                u1 += 1
            # 第二行的元素通过colsum减第一行得到
            low[i] = c - up[i]
        # 返回结果矩阵
        return [up, low]

Explore

在题解中，如果`colsum`数组中值为2的元素个数超过`upper`和`lower`中的最小值，这意味着至少有一行无法容纳必须置为1的元素，因为每个值为2的`colsum`代表这一列的两行都必须是1。如果超过了任一行能承受的最大1的数量，就无法构造一个有效的解，因此返回空数组。

这是基于总数的匹配原则。`colsum`的总和代表整个矩阵中1的总数量。而`upper`和`lower`分别代表第一行和第二行应有的1的总数。如果`colsum`的总和不等于`upper`加`lower`之和，那么就不存在一种方式将1正确分配到两行使得每行的1的数量分别等于`upper`和`lower`，因此无法构建一个有效的矩阵，需要返回空数组。

优先将`colsum`中的值为1的元素分配给第一行（`up`）的策略是尝试先满足一行的需求，以便更容易控制和平衡剩余元素的分配。这样做可以确保在满足第一行的需求后，剩余的1可以直接分配给第二行，从而简化逻辑和实现。如果均匀分配，则可能导致两行同时未达到所需的`upper`和`lower`值，处理起来更复杂。

在这种情况下，所有剩余的`colsum`中值为1的元素必须分配给第二行（`low`）。这是因为第一行（`up`）的和已经达到了其限制`upper`，不能再添加更多的1。因此，剩余的1将全部分配到第二行，以确保整个矩阵的列和符合`colsum`的要求。