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 ，为最大的值。

示例 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)

设二维前缀和res(i, j)表示矩阵matrix中所有满足0 <= x < i且0 <= y < j的元素执行按位异或运算的结果，与一维前缀和类似，要想快速得到res(i, j)，需要知道res(i - 1, j)、res(i, j - 1)、res(i - 1, j - 1)的结果，由此可得：

res[i][j] = res[i - 1][j] ^ res[i][j - 1] ^ res[i - 1][j - 1] ^ matrix[i][j]

实际写代码的时候要对res往外再加一层防止索引越界（对于计算首行/首列（i = 0或j = 0）的情况）

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

        Collections.sort(ans, new Comparator<Integer>() {
            public int compare(Integer num1, Integer num2) {
                return num2 - num1;
            }
        });

        return ans.get(k - 1);
    }
}