行和列中一和零的差值

标签: 数组 矩阵 模拟

难度: 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]]
解释：
- diff[0][0] = onesRow0 + onesCol0 - zerosRow0 - zerosCol0 = 3 + 2 - 0 - 0 = 5
- diff[0][1] = onesRow0 + onesCol1 - zerosRow0 - zerosCol1 = 3 + 2 - 0 - 0 = 5
- diff[0][2] = onesRow0 + onesCol2 - zerosRow0 - zerosCol2 = 3 + 2 - 0 - 0 = 5
- diff[1][0] = onesRow1 + onesCol0 - zerosRow1 - zerosCol0 = 3 + 2 - 0 - 0 = 5
- diff[1][1] = onesRow1 + onesCol1 - zerosRow1 - zerosCol1 = 3 + 2 - 0 - 0 = 5
- diff[1][2] = onesRow1 + onesCol2 - zerosRow1 - zerosCol2 = 3 + 2 - 0 - 0 = 5

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 105
  • 1 <= m * n <= 105
  • grid[i][j] 要么是 0 ，要么是 1 。

Submission

运行时间: 178 ms

内存: 37.1 MB

class Solution:
    def onesMinusZeros(self, grid: List[List[int]]) -> List[List[int]]:
        m, n = len(grid), len(grid[0])
        grid_col = [list(i) for i in zip(*grid)]
        # 预处理
        one_row, zero_row = [], []
        one_col, zero_col = [], []
        for i in range(0, m):
            one_row.append(grid[i].count(1))
            zero_row.append(grid[i].count(0))
        for i in range(0, n):
            one_col.append(grid_col[i].count(1))
            zero_col.append(grid_col[i].count(0))
        # 替换
        for i in range(0, m):
            for j in range(0, n):
                grid[i][j] = one_row[i] + one_col[j] - zero_row[i] - zero_col[j]
        return grid

Explain

此题解的核心思路是首先计算每行和每列中1和0的数量。然后根据题目要求的公式 diff[i][j] = onesRowi + onesColj - zerosRowi - zerosColj，计算每个位置的差值。具体步骤包括：1. 计算每行一的数目和零的数目。2. 计算每列一的数目和零的数目。3. 使用预计算的行和列的一和零的数目，更新矩阵中的每个元素。

时间复杂度: O(m * n)

空间复杂度: O(m + n)

class Solution:
    def onesMinusZeros(self, grid: List[List[int]]) -> List[List[int]]:
        m, n = len(grid), len(grid[0])
        grid_col = [list(i) for i in zip(*grid)] # 转置矩阵，用于方便计算列中的1和0的数量
        # 预处理
        one_row, zero_row = [], [] # 存储每行1和0的计数
        one_col, zero_col = [], [] # 存储每列1和0的计数
        for i in range(0, m):
            one_row.append(grid[i].count(1)) # 计数行中1的数量
            zero_row.append(grid[i].count(0)) # 计数行中0的数量
        for i in range(0, n):
            one_col.append(grid_col[i].count(1)) # 计数列中1的数量
            zero_col.append(grid_col[i].count(0)) # 计数列中0的数量
        # 替换
        for i in range(0, m):
            for j in range(0, n):
                grid[i][j] = one_row[i] + one_col[j] - zero_row[i] - zero_col[j] # 根据公式计算差值并更新
        return grid

Explore

是的，此算法在计算每行每列的1和0的数量时已经考虑了所有可能的边界情况。算法通过直接统计每行和每列中1和0的数量来处理，所以无论是全0行、全1行还是任何其他组合，都能准确计算出每行每列的1和0的数量。

在此算法中，直接在原矩阵`grid`上进行修改不会影响最终结果的计算。这是因为在进行任何修改之前，我们已经预先计算并存储了每行每列中1和0的数量。这些计数是在任何修改发生前完成的，因此即使后续在`grid`上直接修改值，也不会影响使用这些预存计数的正确性。

使用转置矩阵确实会增加额外的空间复杂度，因为我们需要创建一个大小为`n x m`的新矩阵来存储原矩阵的转置。在本题中，如果原矩阵大小为`m x n`，那么转置后的矩阵也会占用`n x m`的空间。因此，总的空间复杂度会从O(1)提升至O(m*n)。在考虑是否使用这种方法时，需要权衡内存使用和编码复杂性的平衡，对于内存敏感的应用或大数据集，可能需要寻找其他不增加额外空间的方法。