Medium

题目描述

给你一个下标从 0 开始的 m x n 二进制矩阵 grid。

我们按照如下过程，创建一个下标从 0 开始的 m x n 差值矩阵 diff：

  • 令第 i 行一的数目为 onesRowi 。
  • 令第 j 列一的数目为 onesColj 。
  • 令第 i 行零的数目为 zerosRowi 。
  • 令第 j 列零的数目为 zerosColj 。
  • diff[i][j] = onesRowi + onesColj - zerosRowi - zerosColj

请你返回差值矩阵 diff 。

示例 1：

输入：grid = [[0,1,1],[1,0,1],[0,0,1]]
输出：[[0,0,4],[0,0,4],[-2,-2,2]]
解释：
- diff[0][0] = onesRow0 + onesCol0 - zerosRow0 - zerosCol0 = 2 + 1 - 1 - 2 = 0
- diff[0][1] = onesRow0 + onesCol1 - zerosRow0 - zerosCol1 = 2 + 1 - 1 - 2 = 0
- diff[0][2] = onesRow0 + onesCol2 - zerosRow0 - zerosCol2 = 2 + 3 - 1 - 0 = 4
- diff[1][0] = onesRow1 + onesCol0 - zerosRow1 - zerosCol0 = 2 + 1 - 1 - 2 = 0
- diff[1][1] = onesRow1 + onesCol1 - zerosRow1 - zerosCol1 = 2 + 1 - 1 - 2 = 0
- diff[1][2] = onesRow1 + onesCol2 - zerosRow1 - zerosCol2 = 2 + 3 - 1 - 0 = 4
- diff[2][0] = onesRow2 + onesCol0 - zerosRow2 - zerosCol0 = 1 + 1 - 2 - 2 = -2
- diff[2][1] = onesRow2 + onesCol1 - zerosRow2 - zerosCol1 = 1 + 1 - 2 - 2 = -2
- diff[2][2] = onesRow2 + onesCol2 - zerosRow2 - zerosCol2 = 1 + 3 - 2 - 0 = 2

示例 2：

输入：grid = [[1,1,1],[1,1,1]]
输出：[[5,5,5],[5,5,5]]

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 10^5
  • 1 <= m * n <= 10^5
  • grid[i][j] 不是 0 就是 1

解题思路

解题思路

这道题的核心是理解差值矩阵的计算公式：diff[i][j] = onesRowi + onesColj - zerosRowi - zerosColj

思路分析

  1. 预处理优化：题目提示我们要重复使用行和列的信息，所以应该先预计算每行和每列的1的个数，避免重复计算。

  2. 数学化简：注意到对于第i行，zerosRowi = n - onesRowi（总列数减去1的个数）；对于第j列，zerosColj = m - onesColj（总行数减去1的个数）。

  3. 公式推导：

    diff[i][j] = onesRowi + onesColj - zerosRowi - zerosColj
          = onesRowi + onesColj - (n - onesRowi) - (m - onesColj)
          = 2 * onesRowi + 2 * onesColj - n - m

  4. 算法步骤：

    • 第一次遍历：统计每行的1的个数
    • 第二次遍历：统计每列的1的个数
    • 第三次遍历：根据简化公式计算差值矩阵

这种预处理方法避免了对每个位置重复计算行列统计，时间复杂度从O(m²n²)优化到O(mn)。

代码实现

class Solution {
public:
    vector<vector<int>> onesMinusZeros(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        
        // 统计每行的1的个数
        vector<int> onesRow(m, 0);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                onesRow[i] += grid[i][j];
            }
        }
        
        // 统计每列的1的个数
        vector<int> onesCol(n, 0);
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < m; i++) {
                onesCol[j] += grid[i][j];
            }
        }
        
        // 计算差值矩阵
        vector<vector<int>> diff(m, vector<int>(n));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                diff[i][j] = 2 * onesRow[i] + 2 * onesCol[j] - m - n;
            }
        }
        
        return diff;
    }
};

class Solution:
    def onesMinusZeros(self, grid: List[List[int]]) -> List[List[int]]:
        m, n = len(grid), len(grid[0])
        
        # 统计每行的1的个数
        ones_row = [sum(row) for row in grid]
        
        # 统计每列的1的个数
        ones_col = [sum(grid[i][j] for i in range(m)) for j in range(n)]
        
        # 计算差值矩阵
        diff = [[2 * ones_row[i] + 2 * ones_col[j] - m - n 
                for j in range(n)] for i in range(m)]
        
        return diff

public class Solution {
    public int[][] OnesMinusZeros(int[][] grid) {
        int m = grid.Length, n = grid[0].Length;
        
        // 统计每行的1的个数
        int[] onesRow = new int[m];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                onesRow[i] += grid[i][j];
            }
        }
        
        // 统计每列的1的个数
        int[] onesCol = new int[n];
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < m; i++) {
                onesCol[j] += grid[i][j];
            }
        }
        
        // 计算差值矩阵
        int[][] diff = new int[m][];
        for (int i = 0; i < m; i++) {
            diff[i] = new int[n];
            for (int j = 0; j < n; j++) {
                diff[i][j] = 2 * onesRow[i] + 2 * onesCol[j] - m - n;
            }
        }
        
        return diff;
    }
}

/**
 * @param {number[][]} grid
 * @return {number[][]}
 */
var onesMinusZeros = function(grid) {
    const m = grid.length, n = grid[0].length;
    
    // 统计每行的1的个数
    const onesRow = new Array(m).fill(0);
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            onesRow[i] += grid[i][j];
        }
    }
    
    // 统计每列的1的个数
    const onesCol = new Array(n).fill(0);
    for (let j = 0; j < n; j++) {
        for (let i = 0; i < m; i++) {
            onesCol[j] += grid[i][j];
        }
    }
    
    // 计算差值矩阵
    const diff = new Array(m).fill().map(() => new Array(n));
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            diff[i][j] = 2 * onesRow[i] + 2 * onesCol[j] - m - n;
        }
    }
    
    return diff;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(m × n)需要遍历整个矩阵三次：统计行、统计列、计算结果
空间复杂度O(m + n)需要额外的数组存储每行和每列的1的个数，不包括结果矩阵的空间

相关题目