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

题目描述：

image.png

解：

还是异或，还是前缀异或，和昨天的区别是这次是一个二维数组，所以相应的，我们需要用二维前缀异或处理数组：
pre(i,j) = pre(i-1,j) xor pre(i,j-1) xor pre(i-1,j-1) xor matrix(i,j)
而后只需要对所有值排序找出要找的第k大即可

  1. class Solution {
  2.     public int kthLargestValue(int[][] matrix, int k) {
  3.         int m = matrix.length, n = matrix[0].length;
  4.         int[][] pre = new int[m + 1][n + 1];
  5.         List<Integer> xor = new ArrayList<Integer>();
  6.         for (int i = 1; i <= m; ++i) {
  7.             for (int j = 1; j <= n; ++j) {
  8.                 pre[i][j] = pre[i - 1][j] ^ pre[i][j - 1] ^ pre[i - 1][j - 1] ^ matrix[i - 1][j - 1];
  9.                 xor.add(pre[i][j]);
  10.             }
  11.         }
  12.         Collections.sort(xor, (num1,num2) -> {
  13.             return num2 - num1;
  14.         });
  15.         return xor.get(k - 1);
  16.     }
  17. }