一、题目

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

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

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

点击查看原题

二、思路

每个(a, b)对应的异或值，是从matrix左上角(0, 0)到右下角(i, j)所有元素的异或值，需要求出所有位置的异或值，然后比较找到第k大的值。
1、求出所有位置的异或值
如果使用暴力法，从左上角(0, 0)到右下角(i, j)所有元素都异或一遍，会有大量的重复计算子问题，现在分析一下，使用dp[i+1][j+1]代表左上角(0, 0)到右下角(i, j)所有元素的异或值：

根据上面的式子，可以的得到：

2、找到第k大的值
可以使用优先队列进行求解，或者自己写一个快排进行查找（效果较好）。

三、代码

class Solution {
    public int kthLargestValue(int[][] matrix, int k) {
        int[][] dp = new int[matrix.length + 1][matrix[0].length + 1];
        // 小根堆
        PriorityQueue<Integer> q = new PriorityQueue<>(k, (o1, o2)-> o1 - o2);
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                dp[i+1][j+1] = dp[i][j] ^ dp[i+1][j] ^ dp[i][j+1] ^ matrix[i][j];
                if (q.size() < k) {    // 当堆的元素数量小于k时添加
                    q.add(dp[i+1][j+1]);
                } else {
                    // 如果堆顶元素小于dp[i+1][j+1]，就删除堆顶元素，并插入dp[i+1][j+1]
                    // 以此保证堆内元素为现在遍历到的最大的k个，且这k个中最小的在上面
                    if (q.peek() < dp[i+1][j+1]) {
                        q.poll();
                        q.add(dp[i+1][j+1]);
                    }
                }
            }
        }
        return q.poll();
    }
}

n和m分别为matrix的行数和列数，时间复杂度为O(nmlog(k))，空间复杂度为O(n*m)。