2021.5.19
最近Leetcode官方连续推荐了3天的异或题目,不把我异或教会不罢休啊,不多说了直接上代码,详细看 Leetcode官方题解吧。
异或运算满足结合律和交换律,且任意数异或自身等于 0。
上式可化简为整体思路还是秉持着使用异或的性质结合前缀和~~~~ 两个相同的数异或结果是0 ,0和任何数异或结果都是它本身,即对一个数做两次重复异或运算。 这个数就会消失。
之前的两道异或题目可以参考:
1. Leecode421:数组中两个数的最大异或值
2. Leetcode1442:形成两个异或相等数组的三元组数目
class Solution {
public:
int kthLargestValue(vector<vector<int>>& matrix, int k) {
//只能是暴力异或,但是要使用前缀和! 二维前缀和,前缀和就是我就算暴力也要知道咋暴力
//就是暴力的结果来自之前的积累
int m=matrix.size(); int n=matrix[0].size();
vector<int> results;
vector<vector<int>> pre(m+1,vector<int>(n+1,0));
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]);
}
}
sort(results.begin(),results.end(),greater<int>()); //greater<int>() 让程序从升序变成降序
return results[k-1];
}
};
这道题目进一步地优化时间复杂度,可以围绕排序来展开,用堆可以更快地实现排序: