LeetCode 1738. Find Kth Largest XOR Coordinate Value

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int kthLargestValue(vector<vector<int>>& matrix, int k) {
        const int m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        vector<int> ans;
        for (int i = 1; i <= m; ++i)
            for (int j = 1; j <= n; ++j)
                ans.emplace_back(dp[i][j] = matrix[i - 1][j - 1] ^ dp[i - 1][j] ^ dp[i][j - 1] ^ dp[i - 1][j - 1]);
        sort(ans.begin(), ans.end(), greater<int>());
        return ans[k - 1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int kthLargestValue(vector<vector<int>>& matrix, int k) {
        const int m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        vector<int> ans;
        for (int i = 1; i <= m; ++i)
            for (int j = 1; j <= n; ++j)
                ans.emplace_back(dp[i][j] = matrix[i - 1][j - 1] ^ dp[i - 1][j] ^ dp[i][j - 1] ^ dp[i - 1][j - 1]);
        nth_element(ans.begin(), ans.begin() + k - 1, ans.end(), greater<int>());
        return ans[k - 1];
    }
};