2711. 对角线上不同值的数量差(中等)

1，问题描述

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：

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

2，初步思考

​ 直接使用前缀和的模式进行处理，先将topLeft、bottomRight矩阵计算处理，然后在进行计算

3，代码处理

package days;

import java.util.HashSet;
import java.util.Set;

public class _2711对角线上不同值的数量差 {

    // 解法2:前缀和
    public int[][] differenceOfDistinctValues_prefix(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] res = new int[m][n];

        for (int i = 0; i < m; ++i) {
            int x = i, y = 0;
            Set<Integer> s = new HashSet<>();
            while (x < m && y < n) {
                res[x][y] += s.size();
                s.add(grid[x][y]);
                x += 1;
                y += 1;
            }
        }

        for (int j = 1; j < n; ++j) {
            int x = 0, y = j;
            Set<Integer> s = new HashSet<>();
            while (x < m && y < n) {
                res[x][y] += s.size();
                s.add(grid[x][y]);
                x += 1;
                y += 1;
            }
        }

        for (int i = 0; i < m; ++i) {
            int x = i, y = n - 1;
            Set<Integer> s = new HashSet<>();
            while (x >= 0 && y >= 0) {
                res[x][y] -= s.size();
                res[x][y] = Math.abs(res[x][y]);
                s.add(grid[x][y]);
                x -= 1;
                y -= 1;
            }
        }

        for (int j = n - 2; j >= 0; --j) {
            int x = m - 1, y = j;
            Set<Integer> s = new HashSet<>();
            while (x >= 0 && y >= 0) {
                res[x][y] -= s.size();
                res[x][y] = Math.abs(res[x][y]);
                s.add(grid[x][y]);
                x -= 1;
                y -= 1;
            }
        }

        return res;
    }


    // 解法1:模拟法
    public int[][] differenceOfDistinctValues_gov(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] res = new int[m][n];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                Set<Integer> s1 = new HashSet<>();
                int x = i + 1, y = j + 1;
                while (x < m && y < n) {
                    s1.add(grid[x][y]);
                    x += 1;
                    y += 1;
                }
                Set<Integer> s2 = new HashSet<>();
                x = i - 1;
                y = j - 1;
                while (x >= 0 && y >= 0) {
                    s2.add(grid[x][y]);
                    x -= 1;
                    y -= 1;
                }
                res[i][j] = Math.abs(s1.size() - s2.size());
            }
        }
        return res;
    }


    // 我自己的方法，类似于前缀和
    public int[][] differenceOfDistinctValues(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        int[][] res = new int[n][m], topLeft = new int[n][m], bottomRight = new int[n][m];
        for (int i = 0; i < n; i++) {
            build(grid, i, 0, topLeft, true);
            build(grid, i, m - 1, bottomRight, false);
        }
        for (int i = 0; i < m; i++) {
            build(grid, 0, i, topLeft, true);
            build(grid, n - 1, i, bottomRight, false);
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                res[i][j] = Math.abs(topLeft[i][j] - bottomRight[i][j]);
            }
        }
        return res;
    }

    private void build(int[][] grid, int i, int j, int[][] matrix, boolean isTopToBottom) {
        Set<Integer> set = new HashSet<>();
        if (isTopToBottom) {
            while (i < matrix.length && j < matrix[0].length) {
                matrix[i][j] = set.size();
                set.add(grid[i][j]);
                i++;
                j++;
            }
        } else {
            while (i >= 0 && j >= 0) {
                matrix[i][j] = set.size();
                set.add(grid[i][j]);
                i--;
                j--;
            }
        }
    }

    public static void main(String[] args) {
        int[][] grid = {
                {15, 42, 48, 22, 36, 47, 13, 23, 31, 41},
                {25, 3, 44, 17, 37, 9, 14, 37, 4, 43},
                {7, 15, 38, 10, 25, 7, 37, 6, 43, 4},
                {50, 9, 14, 36, 35, 36, 44, 17, 10, 44},
                {46, 50, 45, 28, 10, 18, 18, 3, 42, 24},
                {14, 11, 13, 32, 37, 31, 50, 32, 12, 38},
                {44, 24, 42, 9, 32, 40, 8, 20, 46, 39},
                {33, 5, 42, 30, 20, 37, 26, 38, 30, 30},
                {32, 39, 31, 33, 41, 23, 4, 29, 44, 22},
                {8, 8, 11, 21, 9, 2, 37, 19, 30, 37}
        };
        _2711对角线上不同值的数量差 obj = new _2711对角线上不同值的数量差();
        int[][] res = obj.differenceOfDistinctValues(grid);
        for (int[] ints : res) {
            for (int anInt : ints) {
                System.out.print(anInt + " ");
            }
            System.out.println();
        }
    }

}
/**
 * [1,2,3],
 * [3,1,5],
 * [3,2,1]
 * <p>
 * [1,1,0],
 * [1,0,1],
 * [0,1,1]
 */