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

解题思路

这道题采用贪心策略来解决。关键思路是按照列和的值分情况处理：

  1. 预处理检查：首先验证是否有可行解。计算所有列和的总和，这个值必须等于 upper + lower，否则无解。

  2. 分类处理列和：

    • colsum[i] = 0：该列上下行都填 0
    • colsum[i] = 2：该列上下行都填 1，同时 upper 和 lower 都减 1
    • colsum[i] = 1：该列只能有一个 1，需要决定放在上行还是下行

  3. 处理 colsum[i] = 1 的情况：采用贪心策略，优先满足 upper 的需求。如果 upper > 0，就在上行放 1；否则在下行放 1。

  4. 最终验证：处理完所有列后，检查 upper 和 lower 是否都恰好为 0。

这种贪心策略的正确性在于：对于 colsum[i] = 1 的列，我们总是可以通过调整来满足约束，只要总的约束条件满足。

代码实现

class Solution {
public:
    vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& colsum) {
        int n = colsum.size();
        vector<vector<int>> result(2, vector<int>(n, 0));
        
        // 预处理：检查总和是否匹配
        int total = 0;
        for (int sum : colsum) {
            total += sum;
        }
        if (total != upper + lower) {
            return {};
        }
        
        // 处理每一列
        for (int i = 0; i < n; i++) {
            if (colsum[i] == 2) {
                result[0][i] = 1;
                result[1][i] = 1;
                upper--;
                lower--;
            } else if (colsum[i] == 1) {
                if (upper > 0) {
                    result[0][i] = 1;
                    upper--;
                } else {
                    result[1][i] = 1;
                    lower--;
                }
            }
        }
        
        // 检查是否满足约束
        if (upper != 0 || lower != 0) {
            return {};
        }
        
        return result;
    }
};

class Solution:
    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:
        n = len(colsum)
        result = [[0] * n for _ in range(2)]
        
        # 预处理：检查总和是否匹配
        if sum(colsum) != upper + lower:
            return []
        
        # 处理每一列
        for i in range(n):
            if colsum[i] == 2:
                result[0][i] = 1
                result[1][i] = 1
                upper -= 1
                lower -= 1
            elif colsum[i] == 1:
                if upper > 0:
                    result[0][i] = 1
                    upper -= 1
                else:
                    result[1][i] = 1
                    lower -= 1
        
        # 检查是否满足约束
        if upper != 0 or lower != 0:
            return []
        
        return result

public class Solution {
    public IList<IList<int>> ReconstructMatrix(int upper, int lower, int[] colsum) {
        int n = colsum.Length;
        var result = new List<IList<int>>();
        result.Add(new List<int>(new int[n]));
        result.Add(new List<int>(new int[n]));
        
        // 预处理：检查总和是否匹配
        int total = 0;
        foreach (int sum in colsum) {
            total += sum;
        }
        if (total != upper + lower) {
            return new List<IList<int>>();
        }
        
        // 处理每一列
        for (int i = 0; i < n; i++) {
            if (colsum[i] == 2) {
                result[0][i] = 1;
                result[1][i] = 1;
                upper--;
                lower--;
            } else if (colsum[i] == 1) {
                if (upper > 0) {
                    result[0][i] = 1;
                    upper--;
                } else {
                    result[1][i] = 1;
                    lower--;
                }
            }
        }
        
        // 检查是否满足约束
        if (upper != 0 || lower != 0) {
            return new List<IList<int>>();
        }
        
        return result;
    }
}

var reconstructMatrix = function(upper, lower, colsum) {
    const n = colsum.length;
    const result = [new Array(n).fill(0), new Array(n).fill(0)];
    
    // 预处理：检查总和是否匹配
    const total = colsum.reduce((sum, val) => sum + val, 0);
    if (total !== upper + lower) {
        return [];
    }
    
    // 处理每一列
    for (let i = 0; i < n; i++) {
        if (colsum[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历一次 colsum 数组进行预处理，再遍历一次进行构造
空间复杂度O(1)除了结果数组外，只使用了常数额外空间

相关题目