JZX轻语：简

LeetCode 1738 - 找出第K大的异或坐标值

发表于2024年05月26日

#前缀和 #topK #堆

前缀和思路的二维+异或版本，可以就地使用原数组维护前缀和，即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]

闪念标签：LC

题目链接：https://leetcode.cn/problems/find-kth-largest-xor-coordinate-value/