LeetCode 题解工作台
行和列中一和零的差值
给你一个下标从 0 开始的 m x n 二进制矩阵 grid 。 我们按照如下过程，定义一个下标从 0 开始的 m x n 差值矩阵 diff ： 令第 i 行一的数目为 onesRow i 。 令第 j 列一的数目为 onesCol j 。 令第 i 行零的数目为 zerosRow i 。 令第 …
3
题型
7
代码语言
3
相关题
当前训练重点
中等 · 数组·matrix
答案摘要
根据题意模拟即可。 时间复杂度 $O(m \times n)$，忽略答案的空间消耗，空间复杂度 $O(m + n)$。其中 和 分别为矩阵的行数和列数。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·matrix 题型思路
题目描述
给你一个下标从 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.lengthn == grid[i].length1 <= m, n <= 1051 <= m * n <= 105grid[i][j]要么是0，要么是1。
解题思路
方法一：模拟
根据题意模拟即可。
时间复杂度 ，忽略答案的空间消耗，空间复杂度 。其中 和 分别为矩阵的行数和列数。
class Solution:
def onesMinusZeros(self, grid: List[List[int]]) -> List[List[int]]:
m, n = len(grid), len(grid[0])
rows = [0] * m
cols = [0] * n
for i, row in enumerate(grid):
for j, v in enumerate(row):
rows[i] += v
cols[j] += v
diff = [[0] * n for _ in range(m)]
for i, r in enumerate(rows):
for j, c in enumerate(cols):
diff[i][j] = r + c - (n - r) - (m - c)
return diff
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(M * N) |
| 空间 | O(M + N) |
面试官常问的追问
外企场景- question_mark
Ability to optimize calculations by reusing row and column data.
- question_mark
Skill in handling large matrix sizes efficiently.
- question_mark
Understanding of how to manage time and space complexity constraints.
常见陷阱
外企场景- error
Not reusing row and column sums, leading to redundant calculations and inefficient solutions.
- error
Incorrectly handling edge cases where either m or n is 1.
- error
Overcomplicating the problem by not recognizing the need for precomputing sums.
进阶变体
外企场景- arrow_right_alt
Alter the formula to consider other metrics such as sum of all elements in a row and column.
- arrow_right_alt
Extend the problem to work with larger matrices and additional conditions on elements.
- arrow_right_alt
Introduce dynamic changes to the matrix after the initial construction of the difference matrix.