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

[力扣原题链接](https://leetcode-cn.com/problems/find-kth-largest-xor-coordinate-value/)

## 题目

给你一个二维矩阵`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 ，为最大的值。
```

**示例 2:**

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

**示例 3:**

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

**示例 4:**

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

**提示：**

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

## 力扣题解
### 思路与算法

我们用 ⊕ 表示按位异或运算。

由于「按位异或运算」与「加法运算」有着十分相似的性质，它们都满足交换律：`a⊕b=b⊕a`，以及结合律：`(a⊕b)⊕c=a⊕(b⊕c)`

因此我们可以使用「前缀和」这一技巧对按位异或运算的结果进行维护。由于本题中给定的矩阵 `matrix` 是二维的，因此我们需要使用二维前缀和。

设二维前缀和`pre(i,j)` 表示矩阵 `matrix` 中所有满足 `0≤x<i`且`0≤y<j`的元素执行按位异或运算的结果。与一维前缀和类似，要想快速得到 `pre(i,j)`，我们需要已经知道 `pre(i−1,j)`，`pre(i,j−1)`以及 `pre(i−1,j−1)`的结果，即：
`pre(i,j)=pre(i−1,j)⊕pre(i,j−1)⊕pre(i−1,j−1)⊕matrix(i,j)`

下图给出了该二维前缀和递推式的可视化展示。

![](/media/202105/2021-05-20_082408.png)

当我们将`pre(i−1,j)`和`pre(i,j−1)`进行按位异或运算后，由于对一个数`x`异或两次`y`，结果仍然为`x`本身，即：`x⊕y⊕y=x`
因此`pre(i−1,j−1)`对应区域的按位异或结果被抵消，我们需要将其补上，并对位置`(i,j)`的元素进行按位异或运算，这样就得到了`pre(i,j)`。

在得到了所有的二维前缀和之后，我们只需要找出其中第`k`大的元素即为答案。

**细节**
在二维前缀和的计算过程中，如果我们正在计算首行或者首列，即`i=0`或`j=0`，此时例如`pre(i−1,j−1)`是一个超出下标范围的结果。因此我们可以使用一个 `(m+1)×(n+1)`的二维矩阵，将首行和首列空出来赋予默认值`0`，并使用接下来的`m` 行和`n`列存储二维前缀和，这样就不必进行下标范围的判断了。

## 代码

语言：Java

```
class Solution {
    public int kthLargestValue(int[][] matrix, int k) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] pre = new int[m + 1][n + 1];
        List<Integer> results = new ArrayList<Integer>();
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                pre[i][j] = pre[i - 1][j] ^ pre[i][j - 1] ^ pre[i - 1][j - 1] ^ matrix[i - 1][j - 1];
                results.add(pre[i][j]);
            }
        }

Collections.sort(results, new Comparator<Integer>() {
            public int compare(Integer num1, Integer num2) {
                return num2 - num1;
            }
        });
        return results.get(k - 1);
    }
}
```