发表于 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]

• LC 题目链接