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

链接：2711.对角线上不同值的数量差
难度：Medium
标签：数组、哈希表、矩阵
简介：给你一个下标从 0 开始、大小为 m x n 的二维矩阵 grid ，请你求解大小同样为 m x n 的答案矩阵 answer 。

题解 1 - rust

• 编辑时间：2023-05-28
• 执行用时：12ms
• 内存消耗：2.1MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn difference_of_distinct_values(grid: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        use std::collections::HashMap;
        let n = grid.len();
        let m = grid[0].len();
        let mut res = vec![vec![0; m]; n];
        let mut comp = |mut row: usize, mut col: usize| {
            let mut l = HashMap::<i32, i32>::new();
            let mut r = HashMap::<i32, i32>::new();
            let mut nrow = row + 1;
            let mut ncol = col + 1;
            while nrow < n && ncol < m {
                *r.entry(grid[nrow][ncol]).or_insert(0) += 1;
                nrow += 1;
                ncol += 1;
            }
            res[row][col] = (l.len() as i32 - r.len() as i32).abs();
            while row + 1 < n && col + 1 < m {
                *l.entry(grid[row][col]).or_insert(0) += 1;
                row += 1;
                col += 1;
                let item = r.get_mut(&grid[row][col]).unwrap();
                *item -= 1;
                if *item == 0 {
                    r.remove(&grid[row][col]);
                }
                res[row][col] = (l.len() as i32 - r.len() as i32).abs();
            }
        };
        for j in 0..m {
            comp(0, j);
        }
        for i in 1..n {
            comp(i, 0);
        }
        res
    }
}

题解 2 - cpp

• 编辑时间：2023-05-28
• 执行用时：56ms
• 内存消耗：32.2MB
• 编程语言：cpp
• 解法介绍：以每个顶点开始向右下遍历。

class Solution {
public:
    vector<vector<int>> differenceOfDistinctValues(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<int>> res(n, vector<int>(m, 0));
        auto comp = [&](int row, int col) {
            unordered_map<int, int> l, r;
            int nrow = row + 1, ncol = col + 1;
            while (nrow < n && ncol < m) {
                r[grid[nrow][ncol]]++;
                nrow++;
                ncol++;
            }
            res[row][col] = abs((int)l.size() - (int)r.size());
            while (row + 1 < n && col + 1 < m) {
                l[grid[row][col]]++;
                row++;
                col++;
                r[grid[row][col]]--;
                if (r[grid[row][col]] == 0) r.erase(grid[row][col]);
                res[row][col] = abs((int)l.size() - (int)r.size());
            }
        };
        for (int j = 0; j < m; j++)  comp(0, j);
        for (int i = 1; i < n; i++)  comp(i, 0);
        return res;
    }
};;

题解 3 - python

• 编辑时间：2023-05-28
• 执行用时：112ms
• 内存消耗：16.2MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def differenceOfDistinctValues(self, grid: List[List[int]]) -> List[List[int]]:
        n = len(grid)
        m = len(grid[0])
        res = [[0 for _ in range(m)] for _ in range(n)]
        def comp(row: int, col: int):
            l = Counter()
            r = Counter()
            nrow = row + 1
            ncol = col + 1
            while nrow < n and ncol < m:
                r[grid[nrow][ncol]] += 1
                nrow += 1
                ncol += 1
            res[row][col] = abs(len(l) - len(r))
            while row + 1 < n and col + 1 < m:
                l[grid[row][col]] += 1
                row += 1
                col += 1
                r[grid[row][col]] -= 1
                if r[grid[row][col]] == 0:
                    r.pop(grid[row][col])
                res[row][col] = abs(len(l) - len(r))
        for j in range(m):
            comp(0, j)
        for i in range(1, n):
            comp(i, 0)
        return res