[LeetCode解题报告] 1738. 找出第 K 大的异或坐标值

一、 题目

1. 题目描述

1738. 找出第 K 大的异或坐标值

难度：中等

给你一个二维矩阵 matrix 和一个整数 k ，矩阵大小为 m x n 由非负整数组成。

矩阵中坐标 (a, b) 的 值 可由对所有满足 0 <= i <= a < m 且 0 <= j <= b < n 的元素 matrix[i][j]（下标从 0 开始计数）执行异或运算得到。

请你找出 matrix 的所有坐标中第 k 大的值（k 的值从 1 开始计数）。

示例 1：

输入：matrix = [[5,2],[1,6]], k = 1
输出：7
解释：坐标 (0,1) 的值是 5 XOR 2 = 7 ，为最大的值。
1
2
3

示例 2：

输入：matrix = [[5,2],[1,6]], k = 2
输出：5
解释：坐标 (0,0) 的值是 5 = 5 ，为第 2 大的值。
1
2
3

示例 3：

输入：matrix = [[5,2],[1,6]], k = 3
输出：4
解释：坐标 (1,0) 的值是 5 XOR 1 = 4 ，为第 3 大的值。
1
2
3

示例 4：

输入：matrix = [[5,2],[1,6]], k = 4
输出：0
解释：坐标 (1,1) 的值是 5 XOR 2 XOR 1 XOR 6 = 0 ，为第 4 大的值。
1
2
3

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 1000
• 0 <= matrix[i][j] <= 106
• 1 <= k <= m * n

2. 原题链接

链接: 1738. 找出第 K 大的异或坐标值

二、 解题报告

1. 思路分析

 今天的题很简单，一个二维前缀异或和。
1

前置知识：前缀和、dp、二维数组、异或运算
好了，那你已经会这道题了。

• 首先求二维前缀和，我们知道前缀和的状态转移方程是dp[i] = nums[i]+dp[i-1]。

• 二维前缀和的状态转移可以画个图，很简单，我们设dp[i[[j]是以i,j坐标为右下角，以0,0为左上角的子矩阵和。

• 状态转移方程就是dp[i][j] = nums[i][j] 当前数+ dp[i-1][j] 绿色+dp[i][j-1] 红色-dp[i-1][j-1] 紫色
  

• 这里求得是前缀异或和，根据异或的兴致，把上边的加减号都换成异或即可。

• 然后排序取第k大，就做完啦。

2. 复杂度分析

最坏时间复杂度O(n×m)

3. 代码实现

二维前缀异或和。

class Solution:
    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:
        m,n = len(matrix),len(matrix[0])
        # 二维前缀异或和
        presum = [[0]*n for _ in range(m)]
        presum[0] = list(accumulate(matrix[0],xor))
        ans = presum[0][:]

        for i in range(1,m):
            presum[i][0] = presum[i-1][0] ^ matrix[i][0]
            ans.append(presum[i][0])
        
        for i in range(1,m):
            for j in range(1,n):
                presum[i][j] = matrix[i][j] ^ presum[i-1][j] ^ presum[i][j-1] ^ presum[i-1][j-1]
                ans.append(presum[i][j])
        # print(ans)
        return sorted(ans,reverse=True)[k-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

三、 本题小结

1. 二维前缀和变形题。