目录
题目
给你一个二维矩阵 matrix 和一个整数 k ，矩阵大小为 m x n 由非负整数组成。
矩阵中坐标 (a, b) 的 值 可由对所有满足 0 <= i <= a < m 且 0 <= j <= b < n 的元素 matrix[i][j]（下标从 0 开始计数）执行异或运算得到。
请你找出 matrix 的所有坐标中第 k 大的值（k 的值从 1 开始计数）。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-kth-largest-xor-coordinate-value
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
提示：
m == matrix.length
n == matrix[i].length
1 <= m, n <= 1000
0 <= matrix[i][j] <= 106
1 <= k <= m * n
思路
异或轻松搞定。
r[i][j] = r[i-1][j]^r[i][j-1]^r[i-1][j-1]^matrix[i][j]
关键是排序。找第k个。
答案
class Solution {
public:
int kthLargestValue(vector<vector<int>>& matrix, int k) {
//r[i][j] = r[i-1][j]^r[i][j-1]^r[i-1][j-1]^matrix[i][j]
int m = matrix.size();
int n = matrix[0].size();
vector<int> compare;
//r比matric多一行一列
vector<vector<int>> r(m+1,vector<int>(n+1,0));
for(int i = 1;i<=m;i++){
for(int j=1;j<=n;j++){
r[i][j] = r[i-1][j]^r[i][j-1]^r[i-1][j-1]^matrix[i-1][j-1];
compare.push_back(r[i][j]);
}
}
sort(compare.begin(),compare.end(),greater());
return compare[k-1];
}
};
时间复杂度：O(mnlog(mn))。计算二维前缀和的时间复杂度为 O(mn)，排序的时间复杂度为 O(mnlog(mn))，因此总时间复杂度为 O(mnlog(mn))。
空间复杂度：O(mn)，即为存储二维前缀和需要的空间。
小tips：
注意二维数组取大小的方式
int m = matrix.size();
int n = matrix[0].size();
改进
1.nth_element（）
class Solution {
public:
int kthLargestValue(vector<vector<int>>& matrix, int k) {
int m = matrix.size(), n = matrix[0].size();
vector<vector<int>> pre(m + 1, vector<int>(n + 1));
vector<int> results;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
pre[i][j] = pre[i - 1][j] ^ pre[i][j - 1] ^ pre[i - 1][j - 1] ^ matrix[i - 1][j - 1];
results.push_back(pre[i][j]);
}
}
nth_element(results.begin(), results.begin() + k - 1, results.end(), greater<int>());
return results[k - 1];
}
};
时间复杂度：O(mn)。计算二维前缀和的时间复杂度为 O(mn)，快速选择找出第 k 大的元素的期望时间复杂度为O(mn)，最坏情况下时间复杂度为 O((mn)^2)，因此总时间复杂度为 O(mn)。
空间复杂度：O(mn)，即为存储二维前缀和需要的空间
std::nth_element
该函数的作用为将迭代器指向的从_First 到 _last 之间的元素进行二分排序，以_Nth 为分界，前面都比 _Nth小（大），后面都比之大（小）；但是两段内并不有序。
特别适用于找出前k个最大（最小）的元素。
http://www.cplusplus.com/reference/algorithm/nth_element/?kw=nth_element
2. 优先队列（堆）
class Solution {
public:
int kthLargestValue(vector<vector<int>>& mat, int k) {
int m = mat.size(), n = mat[0].size();
int sum[m+1][n+1];
memset(sum, 0, sizeof(sum));
priority_queue<int, vector<int>, greater<int>> pq;
for(int i = 1; i <= m; i++) {
for(int j = 1; j <= n; j++) {
sum[i][j] = sum[i-1][j] ^ sum[i][j-1] ^ sum[i-1][j-1] ^ mat[i-1][j-1];
if(pq.size() < k)
pq.push(sum[i][j]);
else {
if(sum[i][j] > pq.top()) {
pq.pop();
pq.push(sum[i][j]);
}
}
}
}
return pq.top();
}
};
//升序队列
priority_queue <int,vector,greater > q;
//降序队列
priority_queue <int,vector,less >q;
//greater和less是std实现的两个仿函数（就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了）