题目：
给你一个二维矩阵 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：
代码语言：javascript复制输入：matrix = [[5,2],[1,6]], k = 2
输出：5
解释：坐标 (0,0) 的值是 5 = 5 ，为第 2 大的值。
题解：
二维差分 最小堆
前缀和模板 维护k个元素的最小堆
代码语言：javascript复制class Solution {
public:
int prefix[1000][1000];
int kthLargestValue(vector<vector<int>>& matrix, int k) {
int m = matrix.size();
int n = matrix[0].size();
prefix[0][0] = matrix[0][0];
// 处理第一行
for (int i = 1; i < n; i ) {
prefix[0][i] = prefix[0][i - 1] ^ matrix[0][i];
}
// 处理第一列
for (int i = 1; i < m; i ) {
prefix[i][0] = prefix[i - 1][0] ^ matrix[i][0];
}
for (int i = 1; i < m; i ) {
for (int j = 1; j < n; j ) {
prefix[i][j] = prefix[i - 1][j] ^ prefix[i][j - 1] ^ matrix[i][j] ^ prefix[i - 1][j - 1];
}
}
priority_queue<int, vector<int>, std::greater<int>> pq;
for (int i = 0; i < m; i ) {
for (int j = 0; j < n; j ) {
pq.push(prefix[i][j]);
if (pq.size() > k) pq.pop();
}
}
return pq.top();
}
};
二分搜值
每次猜测一个值x，然后遍历前缀和矩阵，统计有多少个元素大于等于x，如果count小于k，那么x肯定不可能是答案，我们将猜测的上界下调至x-1；否则，我们就将猜测的下界调整至x。可以看到问题可以转换为查找最后一个小于等于target的数。因为当查找到大于等于target时要往上不断压缩区间，直到小于等于k为止。
代码语言：javascript复制class Solution {
public:
int prefix[1000][1000];
int m, n;
int kthLargestValue(vector<vector<int>>& matrix, int k) {
m = matrix.size();
n = matrix[0].size();
prefix[0][0] = matrix[0][0];
// 处理第一行
for (int i = 1; i < n; i ) {
prefix[0][i] = prefix[0][i - 1] ^ matrix[0][i];
}
// 处理第一列
for (int i = 1; i < m; i ) {
prefix[i][0] = prefix[i - 1][0] ^ matrix[i][0];
}
for (int i = 1; i < m; i ) {
for (int j = 1; j < n; j ) {
prefix[i][j] = prefix[i - 1][j] ^ prefix[i][j - 1] ^ matrix[i][j] ^ prefix[i - 1][j - 1];
}
}
int left = 0, right = 1e6;
while (left < right) {
int mid = right - (right - left - 1) / 2;
if (count(mid) < k) { // 缩小值
right = mid - 1;
} else {
left = mid;
}
}
return left;
}
int count (int mid) {
int cnt = 0;
for (int i = 0; i < m; i ) {
for (int j = 0; j < n; j ) {
if (prefix[i][j] >= mid) cnt ;
}
}
return cnt;
}
};
本节完~
