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

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:31 2023-09-13 16:06:31 Updated    

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

视频讲解

见【周赛 347】 第二题，欢迎点赞投币！

算法一：模拟

枚举每个位置，往左上和右下遍历，用哈希表统计不同元素个数。

[sol-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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):
            for j in range(n):
                # topLeft
                s = set()
                x, y = i - 1, j - 1
                while x >= 0 and y >= 0:
                    s.add(grid[x][y])
                    x -= 1
                    y -= 1
                sz = len(s)

                # bottomRight
                s.clear()
                x, y = i + 1, j + 1
                while x < m and y < n:
                    s.add(grid[x][y])
                    x += 1
                    y += 1
                ans[i][j] = abs(sz - len(s))
        return ans
[sol-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
func differenceOfDistinctValues(grid [][]int) [][]int {
	m, n := len(grid), len(grid[0])
	ans := make([][]int, m)
	for i := range ans {
		ans[i] = make([]int, n)
		for j := range ans[i] {
			// topLeft
			set := map[int]struct{}{}
			for x, y := i-1, j-1; x >= 0 && y >= 0; {
				set[grid[x][y]] = struct{}{}
				x--
				y--
			}
			sz := len(set)
			
			// bottomRight
			set = map[int]struct{}{}
			for x, y := i+1, j+1; x < m && y < n; {
				set[grid[x][y]] = struct{}{}
				x++
				y++
			}
			ans[i][j] = abs(sz - len(set))
		}
	}
	return ans
}

func abs(x int) int { if x < 0 { return -x }; return x }

复杂度分析

  • 时间复杂度：\mathcal{O}(mn\cdot \min(m,n))，其中 m 和 n 分别为 grid 的行数和列数。
  • 空间复杂度：\mathcal{O}(\min(m,n))。返回值不计入。

算法二：前后缀分解

我们可以从第一行和第一列的每个位置出发，向右下遍历，一边遍历一边用哈希表统计不同元素个数，遍历到 grid}[i][j] 时，哈希表的大小就是 topLeft}[i+1][j+1]。对于 bottomRight 也是同理，从最后一行和最后一列出发去遍历。

代码实现时，可以直接把 topLeft 和 bottomRight 保存到 ans 中。

[sol-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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 k in range(1, m + n):
            min_j = max(n - k, 0)
            max_j = min(m + n - 1 - k, n - 1)
            # topLeft
            s = set()
            for j in range(min_j, max_j):
                i = k + j - n
                s.add(grid[i][j])
                ans[i + 1][j + 1] = len(s)
            # bottomRight
            s.clear()
            for j in range(max_j, min_j, -1):
                i = k + j - n
                s.add(grid[i][j])
                ans[i - 1][j - 1] = abs(ans[i - 1][j - 1] - len(s))
        return ans
[sol-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
func differenceOfDistinctValues(grid [][]int) [][]int {
	m, n := len(grid), len(grid[0])
	ans := make([][]int, m)
	for i := range ans {
		ans[i] = make([]int, n)
	}
	for s := 1; s < m+n; s++ {
		minJ := max(0, n-s)
		maxJ := min(n-1, n-s+m-1)
		// topLeft
		set := map[int]struct{}{}
		for j := minJ; j < maxJ; j++ {
			i := s + j - n
			set[grid[i][j]] = struct{}{}
			ans[i+1][j+1] = len(set)
		}
		// bottomRight
		set = map[int]struct{}{}
		for j := maxJ; j > minJ; j-- {
			i := s + j - n
			set[grid[i][j]] = struct{}{}
			ans[i-1][j-1] = abs(ans[i-1][j-1] - len(set))
		}
	}
	return ans
}

func abs(x int) int { if x < 0 { return -x }; return x }
func min(a, b int) int { if b < a { return b }; return a }
func max(a, b int) int { if b > a { return b }; return a }

复杂度分析

  • 时间复杂度：\mathcal{O}(mn)，其中 m 和 n 分别为 grid 的行数和列数。每个单元格至多访问两次。
  • 空间复杂度：\mathcal{O}(\min(m,n))。返回值不计入。
 Comments
On this page
2711-对角线上不同值的数量差
  1. 视频讲解
  2. 算法一：模拟
  3. 算法二：前后缀分解