Find Kth Largest XOR Coordinate Value（C++找出第 K 大的异或坐标值）

心已赠人 2022-11-10 10:57 100阅读 0赞

解题思路：

（1）先横向再纵向，最后使用优先队列求解

参考网址：[https://leetcode.com/problems/find-kth-largest-xor-coordinate-value/discuss/1032010/Detailed-Explanation-or-C%2B%2B-Solution-or-Easy-Implementation][https_leetcode.com_problems_find-kth-largest-xor-coordinate-value_discuss_1032010_Detailed-Explanation-or-C_2B_2B-Solution-or-Easy-Implementation]

class Solution {
    public:
        int kthLargestValue(vector<vector<int>>& matrix, int k) {
            priority_queue<int,vector<int>, greater<int>> vec;
            
            for(int i=0;i<matrix.size();i++) {
                for(int j=1;j<matrix[i].size();j++) {
                    matrix[i][j]=matrix[i][j]^matrix[i][j-1];
                }
            }
            
            for(int i=0;i<matrix[0].size();i++) {
                for(int j=1;j<matrix.size();j++) {
                    matrix[j][i]=matrix[j][i]^matrix[j-1][i];
                }
            }
            
            for(int i=0;i<matrix.size();i++) {
                for(int j=0;j<matrix[i].size();j++) {
                    if(vec.size()<k) {
                        vec.push(matrix[i][j]);
                    } else if(matrix[i][j]>vec.top()) {
                        vec.push(matrix[i][j]);
                        vec.pop();
                    }
                }
            }
            
            return vec.top();
            
        }
    };

[https_leetcode.com_problems_find-kth-largest-xor-coordinate-value_discuss_1032010_Detailed-Explanation-or-C_2B_2B-Solution-or-Easy-Implementation]: https://leetcode.com/problems/find-kth-largest-xor-coordinate-value/discuss/1032010/Detailed-Explanation-or-C%2B%2B-Solution-or-Easy-Implementation