题目描述
给定一个二维矩阵 matrix
和一个整数 k
,矩阵大小为 m x n
由非负整数组成。
矩阵中坐标 (a, b)
的 值 可由对所有满足 0 <= i <= a < m
且 0 <= j <= b < n
的元素 matrix[i][j]
(下标从 0
开始计数)执行异或运算得到。
找出 matrix
的所有坐标中第 k
大的值(k
的值从 1
开始计数)。
样例
输入:matrix = [[5,2],[1,6]], k = 1
输出:7
解释:坐标 (0,1) 的值是 5 XOR 2 = 7,为最大的值。
输入:matrix = [[5,2],[1,6]], k = 2
输出:5
解释:坐标 (0,0) 的值是 5 = 5,为第 2 大的值。
输入:matrix = [[5,2],[1,6]], k = 3
输出:4
解释:坐标 (1,0) 的值是 5 XOR 1 = 4,为第 3 大的值。
输入:matrix = [[5,2],[1,6]], k = 4
输出:0
解释:坐标 (1,1) 的值是 5 XOR 2 XOR 1 XOR 6 = 0,为第 4 大的值。
限制
m == matrix.length
n == matrix[i].length
1 <= m, n <= 1000
0 <= matrix[i][j] <= 10^6
1 <= k <= m * n
算法
(前缀异或和,堆) $O(mn \log k)$
- 根据公式,$m(i, j) = m(i - 1, j) \text{ XOR } m(i, j - 1) \text{ XOR } m(i - 1, j - 1)$。
- 使用大小为 $k$ 的小根堆,求出元素的第 $k$ 大值。
时间复杂度
- 遍历二维数组一次。
- 每次遍历时,操作堆需要 $O(\log k)$ 的时间。
- 故总时间复杂度为 $O(mn \log k)$。
空间复杂度
- 需要 $O(k)$ 的额外空间存储小根堆。
C++ 代码
class Solution {
public:
int kthLargestValue(vector<vector<int>>& matrix, int k) {
priority_queue<int, vector<int>, greater<int>> heap;
const int m = matrix.size(), n = matrix[0].size();
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) {
if (i > 0) matrix[i][j] ^= matrix[i - 1][j];
if (j > 0) matrix[i][j] ^= matrix[i][j - 1];
if (i > 0 && j > 0) matrix[i][j] ^= matrix[i - 1][j - 1];
if (heap.size() < k) heap.push(matrix[i][j]);
else if (heap.top() < matrix[i][j]) {
heap.pop();
heap.push(matrix[i][j]);
}
}
return heap.top();
}
};
好像就是一个二维前缀和
异或符号打成指数符号了
根据公式,那里
已修正~