跳转至

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

解法

方法一：贪心

我们先创建一个答案数组 \(ans\)，其中 \(ans[0]\) 和 \(ans[1]\) 分别表示矩阵的第一行和第二行。

接下来，从左到右遍历数组 \(colsum\)，对于当前遍历到的元素 \(colsum[j]\)，我们有以下几种情况：

  • 如果 \(colsum[j] = 2\)，那么我们将 \(ans[0][j]\) 和 \(ans[1][j]\) 都置为 \(1\)。此时 \(upper\) 和 \(lower\) 都减去 \(1\)。
  • 如果 \(colsum[j] = 1\)，那么我们将 \(ans[0][j]\) 或 \(ans[1][j]\) 置为 \(1\)。如果 \(upper \gt lower\)，那么我们优先将 \(ans[0][j]\) 置为 \(1\)，否则我们优先将 \(ans[1][j]\) 置为 \(1\)。此时 \(upper\) 或 \(lower\) 减去 \(1\)。
  • 如果 \(colsum[j] = 0\)，那么我们将 \(ans[0][j]\) 和 \(ans[1][j]\) 都置为 \(0\)。
  • 如果 \(upper \lt 0\) 或 \(lower \lt 0\)，那么说明无法构造出满足要求的矩阵，我们返回一个空数组。

遍历结束，如果 \(upper\) 和 \(lower\) 都为 \(0\)，那么我们返回 \(ans\)，否则我们返回一个空数组。

时间复杂度 \(O(n)\)，其中 \(n\) 是数组 \(colsum\) 的长度。忽略答案数组的空间消耗，空间复杂度 \(O(1)\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def reconstructMatrix(
        self, upper: int, lower: int, colsum: List[int]
    ) -> List[List[int]]:
        n = len(colsum)
        ans = [[0] * n for _ in range(2)]
        for j, v in enumerate(colsum):
            if v == 2:
                ans[0][j] = ans[1][j] = 1
                upper, lower = upper - 1, lower - 1
            if v == 1:
                if upper > lower:
                    upper -= 1
                    ans[0][j] = 1
                else:
                    lower -= 1
                    ans[1][j] = 1
            if upper < 0 or lower < 0:
                return []
        return ans if lower == upper == 0 else []

 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 List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {
        int n = colsum.length;
        List<Integer> first = new ArrayList<>();
        List<Integer> second = new ArrayList<>();
        for (int j = 0; j < n; ++j) {
            int a = 0, b = 0;
            if (colsum[j] == 2) {
                a = b = 1;
                upper--;
                lower--;
            } else if (colsum[j] == 1) {
                if (upper > lower) {
                    upper--;
                    a = 1;
                } else {
                    lower--;
                    b = 1;
                }
            }
            if (upper < 0 || lower < 0) {
                break;
            }
            first.add(a);
            second.add(b);
        }
        return upper == 0 && lower == 0 ? List.of(first, second) : List.of();
    }
}

 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
class Solution {
public:
    vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& colsum) {
        int n = colsum.size();
        vector<vector<int>> ans(2, vector<int>(n));
        for (int j = 0; j < n; ++j) {
            if (colsum[j] == 2) {
                ans[0][j] = ans[1][j] = 1;
                upper--;
                lower--;
            }
            if (colsum[j] == 1) {
                if (upper > lower) {
                    upper--;
                    ans[0][j] = 1;
                } else {
                    lower--;
                    ans[1][j] = 1;
                }
            }
            if (upper < 0 || lower < 0) {
                break;
            }
        }
        return upper || lower ? vector<vector<int>>() : ans;
    }
};

 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
30
func reconstructMatrix(upper int, lower int, colsum []int) [][]int {
    n := len(colsum)
    ans := make([][]int, 2)
    for i := range ans {
        ans[i] = make([]int, n)
    }
    for j, v := range colsum {
        if v == 2 {
            ans[0][j], ans[1][j] = 1, 1
            upper--
            lower--
        }
        if v == 1 {
            if upper > lower {
                upper--
                ans[0][j] = 1
            } else {
                lower--
                ans[1][j] = 1
            }
        }
        if upper < 0 || lower < 0 {
            break
        }
    }
    if upper != 0 || lower != 0 {
        return [][]int{}
    }
    return ans
}

 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
function reconstructMatrix(upper: number, lower: number, colsum: number[]): number[][] {
    const n = colsum.length;
    const ans: number[][] = Array(2)
        .fill(0)
        .map(() => Array(n).fill(0));
    for (let j = 0; j < n; ++j) {
        if (colsum[j] === 2) {
            ans[0][j] = ans[1][j] = 1;
            upper--;
            lower--;
        } else if (colsum[j] === 1) {
            if (upper > lower) {
                ans[0][j] = 1;
                upper--;
            } else {
                ans[1][j] = 1;
                lower--;
            }
        }
        if (upper < 0 || lower < 0) {
            break;
        }
    }
    return upper || lower ? [] : ans;
}

评论