1738. Find Kth Largest XOR Coordinate Value

by

1738. Find Kth Largest XOR Coordinate Value

Medium

You are given a 2D matrix of size m x n, consisting of non-negative integers. You are also given an integer k.

The value of coordinate (a, b) of the matrix is the XOR of all matrix[i][j] where 0 <= i <= a < m and 0 <= j <= b < n (0-indexed).

Find the kth largest value (1-indexed) of all the coordinates of matrix.

Example 1:

Input: matrix = [[5,2],[1,6]], k = 1
Output: 7
Explanation: The value of coordinate (0,1) is 5 XOR 2 = 7, which is the largest value.

Example 2:

Input: matrix = [[5,2],[1,6]], k = 2
Output: 5
Explanation: The value of coordinate (0,0) is 5 = 5, which is the 2nd largest value.

Example 3:

Input: matrix = [[5,2],[1,6]], k = 3
Output: 4
Explanation: The value of coordinate (1,0) is 5 XOR 1 = 4, which is the 3rd largest value.

Example 4:

Input: matrix = [[5,2],[1,6]], k = 4
Output: 0
Explanation: The value of coordinate (1,1) is 5 XOR 2 XOR 1 XOR 6 = 0, which is the 4th largest value.

Constraints:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 1000
  • 0 <= matrix[i][j] <= 106
  • 1 <= k <= m * n

思路

（略）

（LeetCode 的提交显示：记录全部 coordinate_value 后调 std::nth_element 比 最小堆 快……）

（用 std::nth_element 的话大概是在 300 ms 级别。）

class Solution {
public:
    int kthLargestValue(vector<vector<int>>& matrix, int k) {
        int m = matrix.size();
        int n = matrix[0].size();
        
        vector<int> row_coordinate_value(n, 0);
        vector<int> row_xor_buf(n, 0);
        priority_queue<int, vector<int>, greater<int>> min_heap;
        for (int i = 0; i < m; ++i) {
            row_xor_buf[0] = matrix[i][0];
            if (i == 0) {
                row_coordinate_value[0] = row_xor_buf[0];
            } else {
                row_coordinate_value[0] = row_xor_buf[0] ^ row_coordinate_value[0];
            }
            
            if (min_heap.size() < k) {
                min_heap.push(row_coordinate_value[0]);
            } else if (min_heap.top() < row_coordinate_value[0]) {
                min_heap.pop();
                min_heap.push(row_coordinate_value[0]);
            }

            for (int j = 1; j < n; ++j) {
                row_xor_buf[j] = row_xor_buf[j - 1] ^ matrix[i][j];
                row_coordinate_value[j] = row_xor_buf[j] ^ row_coordinate_value[j];

                min_heap.push(row_coordinate_value[j]);
                if (min_heap.size() > k) {
                    min_heap.pop();
                }
            }
        }

        return min_heap.top();
    }
};

Runtime: 552 ms, faster than 38.19% of C++ online submissions for Find Kth Largest XOR Coordinate Value.

Memory Usage: 99.2 MB, less than 84.59% of C++ online submissions for Find Kth Largest XOR Coordinate Value.

Leave a Comment