当前位置：首页 > news >正文

解题思路：LeetCode 2711. 对角线上不同值的数量差

news 来源：原创 2025/7/26 9:01:09

解题思路：LeetCode 2711. 对角线上不同值的数量差

在LeetCode的题目2711中，我们需要计算一个矩阵中每个单元格的左上角对角线和右下角对角线上不同值的数量差。这个问题可以通过暴力法解决，但效率较低。本文将介绍一种更高效的解决方案，并通过Python代码实现。

问题描述

给定一个大小为 m x n 的二维矩阵 grid，我们需要求解一个新的答案矩阵 answer，其中每个单元格 (r, c) 的值是该单元格左上角对角线上不同值的数量与右下角对角线上不同值的数量之差的绝对值。

输入输出格式

输入：一个二维数组 grid。
输出：一个新的二维数组 answer，大小与 grid 相同。

示例

示例 1

输入：grid = [[1,2,3],[3,1,5],[3,2,1]]

输出：[[1,1,0],[1,0,1],[0,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。

解题思路

暴力法

暴力法的核心思想是直接计算每个单元格的左上对角线和右下对角线上的不同值数量，然后求差的绝对值。这种方法简单直观，但效率较低，尤其是在矩阵较大时。

优化方法

为了提高效率，我们可以利用对角线的性质，预先计算每条对角线上的不同值数量，从而避免重复计算。

预处理对角线上的不同值数量：
- 对于每条左上对角线，从矩阵的右下角开始向上遍历，计算每条对角线上的不同值数量。
- 对于每条右下对角线，从矩阵的左上角开始向下遍历，计算每条对角线上的不同值数量。
存储对角线上的不同值数量：
- 使用两个二维数组 topLeft 和 bottomRight 分别存储每个单元格的左上对角线和右下对角线上的不同值数量。
计算答案矩阵：
- 遍历矩阵 grid，根据 topLeft 和 bottomRight 的值计算答案矩阵 ans。

Python代码实现

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 k in range(m + n):min_j = max(0, n - k)max_j = min(n - 1, m - 1 - k + n)a = set()for j in range(min_j, max_j + 1):ans[k + j - n][j] = len(a)a.add(grid[k + j - n][j])a.clear()for j in range(max_j, min_j - 1, -1):ans[k + j - n][j] = abs(ans[k + j - n][j] - len(a))a.add(grid[k + j - n][j])return ans

总结

通过预处理对角线上的不同值数量，我们可以显著减少重复计算，从而优化算法的时间复杂度。优化后的算法在处理大规模矩阵时更加高效，同时保持了代码的简洁性。希望这篇博客能帮助你更好地理解和解决这个问题。