Halo

A magic place for coding

0%

LeetCode解题报告(500)-- 1738. Find Kth Largest XOR Coordinate Value

Problem

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:

1
2
3
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:

1
2
3
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:

1
2
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.

Constraints:

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

Analysis

  这道题目给出一个矩阵,定义每个位置的value是以它和左上角为顶点的矩阵内所有元素的异或结果。对于矩阵中,要求子矩阵的和、异或结果等,优先考虑的就是矩阵前缀和。其基本公式为preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] + preSum[i][j] - preSum[i - 1][j - 1]

  这道题目基本就按照上面的公式就能快速求得每个位置的value,然后是求第k大的value。求第k大数一般有两种方法,一个是用priority queue,另一种是类似于快排的方法。这里因为value是随着不断产生的,更加适合用priority queue,所以我们维护前k个元素即可。

Solution

  无。


Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
int kthLargestValue(vector<vector<int>>& matrix, int k) {
priority_queue<int, vector<int>, greater<int>> pq;
int m = matrix.size(), n = matrix[0].size();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
int sum = matrix[i][j];
if (i > 0) {
sum ^= matrix[i - 1][j];
}
if (j > 0) {
sum ^= matrix[i][j - 1];
}
if (i > 0 && j > 0) {
sum ^= matrix[i - 1][j - 1];
}
matrix[i][j] = sum;
pq.push(sum);
if (pq.size() > k) {
pq.pop();
}
}
}
return pq.top();
}
};

Summary

  这道题目是矩阵preSum加求第k大数两个知识点的结合,都不难。这道题目的分享到这里,感谢你的支持!

Welcome to my other publishing channels