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

链接：1738.找出第K大的异或坐标值
难度：Medium
标签：位运算、数组、分治、矩阵、前缀和、快速选择、排序、堆（优先队列）
简介：请你找出 matrix 的所有坐标中第 k 大的值（k 的值从 1 开始计数）。

题解 1 - typescript

• 编辑时间：2021-05-19
• 执行用时：736ms
• 内存消耗：105.1MB
• 编程语言：typescript
• 解法介绍：前缀和。

function kthLargestValue(matrix: number[][], k: number): number {
  const rowLen = matrix.length;
  const colLen = matrix[0].length;
  const prefixSumList: number[][] = new Array(rowLen + 1)
    .fill(0)
    .map(_ => new Array(colLen + 1).fill(0));
  const list: number[] = [];
  for (let row = 1; row <= rowLen; row++) {
    for (let col = 1; col <= colLen; col++) {
      list.push(
        (prefixSumList[row][col] =
          prefixSumList[row - 1][col] ^
          prefixSumList[row][col - 1] ^
          prefixSumList[row - 1][col - 1] ^
          matrix[row - 1][col - 1])
      );
    }
  }
  return list.sort((a, b) => b - a)[k - 1];
}

题解 2 - python

• 编辑时间：2024-05-26
• 执行用时：770ms
• 内存消耗：61.8MB
• 编程语言：python
• 解法介绍：前缀和存储异或值后，利用堆排序。

class Solution:
    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:
        n, m = len(matrix), len(matrix[0])
        sums = [[0] * (m + 1) for _ in range(n + 1)]
        q = []
        for i in range(1, n + 1):
            for j in range(1, m + 1):
                sums[i][j] = sums[i - 1][j] ^ sums[i][j - 1] ^ sums[i - 1][j - 1] ^ matrix[i - 1][j - 1]
                heappush(q, -sums[i][j])
        for _ in range(k - 1): heappop(q)
        return -q[0]