对角线上不同值的数量差

标签: 数组 哈希表 矩阵

难度: Medium

给你一个下标从 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.length
  • n == grid[i].length
  • 1 <= m, n, grid[i][j] <= 50

Submission

运行时间: 51 ms

内存: 16.3 MB

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):
            x,y=i,0
            mp=set()
            while x<m and y<n:
                ans[x][y]=len(mp)
                mp.add(grid[x][y])
                x+=1
                y+=1
        for j in range(1,n):
            x,y=0,j
            mp=set()
            while x<m and y<n:
                ans[x][y]=len(mp)
                mp.add(grid[x][y])
                x+=1
                y+=1
        for i in range(m-1,-1,-1):
            x,y=i,n-1
            mp=set()
            while x>=0 and y>=0:
                ans[x][y]=abs(ans[x][y]-len(mp))
                mp.add(grid[x][y])
                x-=1
                y-=1
        for j in range(n-2,-1,-1):
            x,y=m-1,j
            mp=set()
            while x>=0 and y>=0:
                ans[x][y]=abs(ans[x][y]-len(mp))
                mp.add(grid[x][y])
                x-=1
                y-=1
        return ans

Explain

此题解方法通过遍历矩阵中的所有对角线来计算左上角和右下角的对角线上的不同值数量。首先，使用四个独立的循环来分别处理矩阵的四个边界开始的对角线：首先是从上边界开始的左上到右下的对角线（两个循环），接着是从右边界和底边界开始的右下到左上的对角线（两个循环）。每个循环中使用一个集合来存储遍历过程中遇到的不同的值，并在每个单元格更新answer矩阵中的对应值。最后，根据左上和右下的值计算其差的绝对值。

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

空间复杂度: O(min(m, n))

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):
            x, y = i, 0
            mp = set()  # 使用集合来存储遇到的不同值
            while x < m and y < n:
                ans[x][y] = len(mp)
                mp.add(grid[x][y])
                x += 1
                y += 1
        for j in range(1, n):
            x, y = 0, j
            mp = set()
            while x < m and y < n:
                ans[x][y] = len(mp)
                mp.add(grid[x][y])
                x += 1
                y += 1
        # 计算右下到左上的对角线的不同值数量并计算最终结果
        for i in range(m - 1, -1, -1):
            x, y = i, n - 1
            mp = set()
            while x >= 0 and y >= 0:
                ans[x][y] = abs(ans[x][y] - len(mp))  # 更新结果矩阵的值
                mp.add(grid[x][y])
                x -= 1
                y -= 1
        for j in range(n - 2, -1, -1):
            x, y = m - 1, j
            mp = set()
            while x >= 0 and y >= 0:
                ans[x][y] = abs(ans[x][y] - len(mp))
                mp.add(grid[x][y])
                x -= 1
                y -= 1
        return ans  # 返回答案矩阵

Explore

在处理对角线不同值的计算时，集合（Set）提供了一种快速有效的方式来确保值的唯一性，即自动处理重复值。集合的主要操作包括添加元素和检查元素是否存在，这两种操作通常都能在平均常数时间内完成，这使得它非常适合于此类问题，其中需要频繁地检查和添加不同的元素。相比之下，如果使用列表（List）或数组（Array），则每次添加新元素时都需先遍历已有元素以避免重复，这会导致时间复杂度显著增加。

题解中通过分别维护两个独立的集合来处理从左上到右下和从右下到左上的对角线。这两个集合在遍历时各自独立，确保了在计算每个方向上的对角线时，都是从新的集合开始，避免了重复计数的问题。同时，在计算结果矩阵`ans[r][c]`时使用绝对值来处理两个方向上不同值的数量之差，这进一步确保了不会由于遍历顺序或重复元素影响最终结果的正确性。

在矩阵行数和列数差异较大的情况下，方法依然保持效率，因为每次遍历都是沿着单独的对角线从某一边界到另一边界。虽然某些对角线可能较短（特别是当接近矩阵的角落时），但每个元素仍然只被访问一次，不会造成重复遍历。此外，对于每个方向的对角线，遍历是从边界开始，直到另一边界结束，有效地利用了每个元素。

这种方法允许在遍历对角线时即时更新答案矩阵，这样可以边计算边更新，避免了在所有数据收集完毕后再进行一次整体的复杂计算，这样可以降低时间复杂度和空间复杂度。实时更新结果也使得代码结构更简洁，逻辑更清晰，易于理解和维护。此外，这种方法避免了可能的错误和复杂性，因为所有必要的信息在访问某个单元格时都是最新的，并立即应用到答案矩阵中。