LeetCode 题解工作台
对角线上不同值的数量差
给你一个下标从 0 开始、大小为 m x n 的二维矩阵 grid ，请你求解大小同样为 m x n 的答案矩阵 answer 。 矩阵 answer 中每个单元格 (r, c) 的值可以按下述方式进行计算： 令 topLeft[r][c] 为矩阵 grid 中单元格 (r, c) 左上角对角线上 …
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
我们可以按照题目描述的流程模拟，计算出每个单元格的左上角对角线上不同值的数量 和右下角对角线上不同值的数量 ，然后计算它们的差值 $|tl - br|$。 时间复杂度 $O(m \times n \times \min(m, n))$，空间复杂度 $O(m \times n)$。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个下标从 0 开始、大小为 m x n 的二维矩阵 grid ，请你求解大小同样为 m x n 的答案矩阵 answer 。
矩阵 answer 中每个单元格 (r, c) 的值可以按下述方式进行计算：
- 令
topLeft[r][c]为矩阵grid中单元格(r, c)左上角对角线上 不同值 的数量。 - 令
bottomRight[r][c]为矩阵grid中单元格(r, c)右下角对角线上 不同值 的数量。
然后 answer[r][c] = |topLeft[r][c] - bottomRight[r][c]| 。
返回矩阵 answer 。
矩阵对角线 是从最顶行或最左列的某个单元格开始，向右下方向走到矩阵末尾的对角线。
如果单元格 (r1, c1) 和单元格 (r, c) 属于同一条对角线且 r1 < r ，则单元格 (r1, c1) 属于单元格 (r, c) 的左上对角线。类似地，可以定义右下对角线。
示例 1：
输入：grid = [[1,2,3],[3,1,5],[3,2,1]] 输出：[[1,1,0],[1,0,1],[0,1,1]] 解释：第 1 个图表示最初的矩阵 grid 。 第 2 个图表示对单元格 (0,0) 计算，其中蓝色单元格是位于右下对角线的单元格。 第 3 个图表示对单元格 (1,2) 计算，其中红色单元格是位于左上对角线的单元格。 第 4 个图表示对单元格 (1,1) 计算，其中蓝色单元格是位于右下对角线的单元格，红色单元格是位于左上对角线的单元格。 - 单元格 (0,0) 的右下对角线包含 [1,1] ，而左上对角线包含 [] 。对应答案是 |1 - 0| = 1 。 - 单元格 (1,2) 的右下对角线包含 [] ，而左上对角线包含 [2] 。对应答案是 |0 - 1| = 1 。 - 单元格 (1,1) 的右下对角线包含 [1] ，而左上对角线包含 [1] 。对应答案是 |1 - 1| = 0 。 其他单元格的对应答案也可以按照这样的流程进行计算。
示例 2：
输入：grid = [[1]] 输出：[[0]] 解释：- 单元格 (0,0) 的右下对角线包含 [] ，左上对角线包含 [] 。对应答案是 |0 - 0| = 0 。
提示：
m == grid.lengthn == grid[i].length1 <= m, n, grid[i][j] <= 50
解题思路
方法一：模拟
我们可以按照题目描述的流程模拟，计算出每个单元格的左上角对角线上不同值的数量 和右下角对角线上不同值的数量 ，然后计算它们的差值 。
时间复杂度 ，空间复杂度 。
class Solution:
def differenceOfDistinctValues(self, grid: List[List[int]]) -> List[List[int]]:
m, n = len(grid), len(grid[0])
ans = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n):
x, y = i, j
s = set()
while x and y:
x, y = x - 1, y - 1
s.add(grid[x][y])
tl = len(s)
x, y = i, j
s = set()
while x + 1 < m and y + 1 < n:
x, y = x + 1, y + 1
s.add(grid[x][y])
br = len(s)
ans[i][j] = abs(tl - br)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Ability to optimize matrix traversal with hash sets for distinct values.
- question_mark
Understanding of how to use efficient data structures like hash sets in matrix-related problems.
- question_mark
Experience with solving problems involving matrix diagonals and distinct value counting.
常见陷阱
外企场景- error
Overcomplicating the problem by failing to recognize the need for efficient scanning.
- error
Misunderstanding the concept of diagonals, leading to incorrect traversal logic.
- error
Failing to handle edge cases such as single-row or single-column matrices.
进阶变体
外企场景- arrow_right_alt
Modify the problem to handle larger matrices efficiently.
- arrow_right_alt
Consider cases where the diagonals can be in different directions.
- arrow_right_alt
Optimize the approach for matrices with larger values or constraints.