Medium

题目描述

给你一个大小为 m x n 的二维网格 grid，你需要求出一个大小为 m x n 的矩阵 answer。

单元格 answer[r][c] 的计算方法是查看单元格 grid[r][c] 的对角线值：

  • 设 leftAbove[r][c] 为单元格 grid[r][c] 左上对角线上不同值的数量，不包括 grid[r][c] 本身。
  • 设 rightBelow[r][c] 为单元格 grid[r][c] 右下对角线上不同值的数量，不包括 grid[r][c] 本身。
  • 那么 answer[r][c] = |leftAbove[r][c] - rightBelow[r][c]|。

矩阵对角线是从最顶行或最左列的某个单元格开始，沿右下方向直到矩阵边界的对角线单元格。

示例 1：

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

示例 2：

输入：grid = [[1]]
输出：[[0]]

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n, grid[i][j] <= 50

解题思路

解题思路

这道题目要求我们对于每个位置 (r,c)，计算其左上对角线和右下对角线上不同元素的数量差的绝对值。

核心思路：

  1. 理解对角线：对于位置 (r,c)，其所在的对角线可以通过 r-c 的值来标识。同一条对角线上的所有点都有相同的 r-c 值。

  2. 分别处理两个方向：

    • 左上对角线：从当前位置向左上方向遍历，即 (r-1,c-1), (r-2,c-2), …
    • 右下对角线：从当前位置向右下方向遍历，即 (r+1,c+1), (r+2,c+2), …

  3. 使用集合统计不同值：对于每个方向，使用 Set 来统计遍历过程中遇到的不同元素个数。

算法步骤：

  1. 遍历矩阵中的每个位置 (r,c)
  2. 对于每个位置，分别向左上和右下方向遍历同一条对角线
  3. 使用两个集合分别记录左上和右下方向的不同元素
  4. 计算两个集合大小的差值的绝对值

这种方法的时间复杂度虽然看似较高，但由于矩阵大小限制在50x50以内，实际性能完全可以接受。

代码实现

class Solution {
public:
    vector<vector<int>> differenceOfDistinctValues(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> answer(m, vector<int>(n));
        
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                unordered_set<int> leftAbove, rightBelow;
                
                // 左上对角线
                for (int i = r - 1, j = c - 1; i >= 0 && j >= 0; i--, j--) {
                    leftAbove.insert(grid[i][j]);
                }
                
                // 右下对角线
                for (int i = r + 1, j = c + 1; i < m && j < n; i++, j++) {
                    rightBelow.insert(grid[i][j]);
                }
                
                answer[r][c] = abs((int)leftAbove.size() - (int)rightBelow.size());
            }
        }
        
        return answer;
    }
};

class Solution:
    def differenceOfDistinctValues(self, grid: List[List[int]]) -> List[List[int]]:
        m, n = len(grid), len(grid[0])
        answer = [[0] * n for _ in range(m)]
        
        for r in range(m):
            for c in range(n):
                left_above = set()
                right_below = set()
                
                # 左上对角线
                i, j = r - 1, c - 1
                while i >= 0 and j >= 0:
                    left_above.add(grid[i][j])
                    i -= 1
                    j -= 1
                
                # 右下对角线
                i, j = r + 1, c + 1
                while i < m and j < n:
                    right_below.add(grid[i][j])
                    i += 1
                    j += 1
                
                answer[r][c] = abs(len(left_above) - len(right_below))
        
        return answer

public class Solution {
    public int[][] DifferenceOfDistinctValues(int[][] grid) {
        int m = grid.Length, n = grid[0].Length;
        int[][] answer = new int[m][];
        for (int i = 0; i < m; i++) {
            answer[i] = new int[n];
        }
        
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                HashSet<int> leftAbove = new HashSet<int>();
                HashSet<int> rightBelow = new HashSet<int>();
                
                // 左上对角线
                for (int i = r - 1, j = c - 1; i >= 0 && j >= 0; i--, j--) {
                    leftAbove.Add(grid[i][j]);
                }
                
                // 右下对角线
                for (int i = r + 1, j = c + 1; i < m && j < n; i++, j++) {
                    rightBelow.Add(grid[i][j]);
                }
                
                answer[r][c] = Math.Abs(leftAbove.Count - rightBelow.Count);
            }
        }
        
        return answer;
    }
}

var differenceOfDistinctValues = function(grid) {
    const m = grid.length, n = grid[0].length;
    const answer = Array(m).fill().map(() => Array(n).fill(0));
    
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            const leftAbove = new Set();
            const rightBelow = new Set();
            
            // 左上对角线
            for (let i = r - 1, j = c - 1; i >= 0 && j >= 0; i--, j--) {
                leftAbove.add(grid[i][j]);
            }
            
            // 右下对角线
            for (let i = r + 1, j = c + 1; i < m && j < n; i++, j++) {
                rightBelow.add(grid[i][j]);
            }
            
            answer[r][c] = Math.abs(leftAbove.size - rightBelow.size);
        }
    }
    
    return answer;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(m × n × (m + n))，对于每个位置需要遍历对角线，最坏情况下对角线长度为 m + n
空间复杂度O(min(m, n))，每次计算时集合中最多存储一条对角线上的所有不同元素