JZX轻语：简
LeetCode 1738 - 找出第K大的异或坐标值
发表于2024年05月26日
前缀和思路的二维+异或版本，可以就地使用原数组维护前缀和，即matrix[i][j]为矩阵matrix中(0, 0)到(i, j)的异或和，且matrix[i][j] = matrix[i-1][j] ^ matrix[i][j-1] ^ matrix[i-1][j-1] ^ matrix[i][j](因为matrix[i - 1][j - 1]实际上都包含在matrix[i-1][j]和matrix[i][j-1]中，两者异或后相互抵消了，需要再异或一次)。然后使用排序或者堆来维护前k大的值即可。
import heapq
class Solution:
def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:
pq = []
for i in range(len(matrix)):
for j in range(len(matrix[i])):
matrix[i][j] = (
(matrix[i - 1][j] if i > 0 else 0) ^
(matrix[i][j - 1] if j > 0 else 0) ^
(matrix[i - 1][j - 1] if i > 0 and j > 0 else 0) ^
matrix[i][j]
)
heapq.heappush(pq, matrix[i][j])
if len(pq) > k:
heapq.heappop(pq)
return pq[0]