题目
给你一个二维矩阵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.lengthn == matrix[i].length1 <= m, n <= 10000 <= matrix[i][j] <= 1061 <= 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)
下图给出了该二维前缀和递推式的可视化展示。
当我们将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);
}
}
