算法
(前缀和、优先队列) $O(nm\log k)$
首先,如何求出每个坐标的异或值?我们可以用类似二维前缀和的办法求。但 $\oplus$ 本身就是自己的逆运算,所以不需要像二维前缀和那样有 +
有 -
,直接全用 $\oplus$ 即可。
一共 $nm = 1e6$ 个数,我们要找出第 $k$ 大的数,可以借助小根堆,维护 $k$ 个最大的元素。
C++ 代码
class Solution {
public:
int kthLargestValue(vector<vector<int>>& matrix, int k) {
int n = matrix.size(), m = matrix[0].size();
vector<vector<int>> a(n + 1, vector<int>(m + 1));
priority_queue<int, vector<int>, greater<int>> q;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
a[i][j] = a[i - 1][j] ^ a[i][j - 1] ^ a[i - 1][j - 1] ^ matrix[i - 1][j - 1];
q.emplace(a[i][j]);
if (q.size() > k) q.pop();
}
}
return q.top();
}
};