首页算法

2711. 对角线上不同值的数量差

难度中等

给你一个下标从 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：

img

输入：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

# 模拟

class Solution {
    public int[][] differenceOfDistinctValues(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        int[][] ans = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                Set<Integer> set = new HashSet<>();
                // 左上
                int l = 0;
                for (int i1 = i - 1, j1 = j - 1; i1 >= 0 && j1 >= 0; i1--, j1--) {
                    if (set.contains(grid[i1][j1])) {
                        continue;
                    }
                    set.add(grid[i1][j1]);
                    l++;
                }
                // 右下
                int r = 0;
                set.clear();
                for (int i1 = i + 1, j1 = j + 1; i1 < n && j1 < m; i1++, j1++) {
                    if (set.contains(grid[i1][j1])) {
                        continue;
                    }
                    set.add(grid[i1][j1]);
                    r++;
                }
                ans[i][j] = Math.abs(l - r);
            }
        }
        return ans;
    }
}

# 前后缀分解 + 哈希表

对于前缀，采用哈希表保存每一层的元素。

  • 若此时位置为 i,ji,j。获取上一层的哈希表 set[i−1][j−1]set[i-1][j-1]

    此时 left[i][j]=set[i−1][j−1]left[i][j]=set[i -1][j-1]，并更新当前层的哈希表 set[i][j]=set[i−1][j−1]set[i][j] = set[i - 1][j - 1]

对于后缀也同理。

由于每一层哈希表只更上一层有关，可采用滚动哈希表。

class Solution {
    public int[][] differenceOfDistinctValues(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        int[][] ans = new int[n][m];
        // 左上角不同值的数量
        int[][] left = new int[n][m];
        Set<Integer>[] setl = new HashSet[m];
        for (int i = 0; i < m; i++) {
            setl[i] = new HashSet<>();
            setl[i].add(grid[0][i]);
        }
        for (int i = 1; i < n; i++) {
            Set<Integer> temp = new HashSet<>();
            temp.add(grid[i - 1][0]);
            for (int j = 1; j < m; j++) {
                left[i][j] = temp.size();
                temp.add(grid[i][j]);
                Set<Integer> t = setl[j];
                setl[j] = temp;
                temp = t;
            }
        }
        // 右下角不同值的数量
        int[][] right = new int[n][m];
        Set<Integer>[] setr = new HashSet[m];
        for (int i = 0; i < m; i++) {
            setr[i] = new HashSet<>();
            setr[i].add(grid[n - 1][i]);
        }
        for (int i = n - 2; i >= 0; i--) {
            Set<Integer> temp = new HashSet<>();
            temp.add(grid[i + 1][m - 1]);
            for (int j = m - 2; j >= 0; j--) {
                right[i][j] = temp.size();
                temp.add(grid[i][j]);
                Set<Integer> t = setr[j];
                setr[j] = temp;
                temp = t;
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                ans[i][j] = Math.abs(left[i][j] - right[i][j]);
            }
        }
        return ans;
    }
}