找出第 K 大的异或坐标值

标签: 位运算 数组 分治 矩阵 前缀和 快速选择 堆（优先队列）

难度: Medium

给你一个二维矩阵 matrix 和一个整数 k ，矩阵大小为 m x n 由非负整数组成。

矩阵中坐标 (a, b) 的 值 可由对所有满足 0 <= i <= a < m 且 0 <= j <= b < n 的元素 matrix[i][j]（下标从 0 开始计数）执行异或运算得到。

请你找出 matrix 的所有坐标中第 k 大的值（k 的值从 1 开始计数）。

 

示例 1：

输入：matrix = [[5,2],[1,6]], k = 1
输出：7
解释：坐标 (0,1) 的值是 5 XOR 2 = 7 ，为最大的值。

示例 2：

输入：matrix = [[5,2],[1,6]], k = 2
输出：5
解释：坐标 (0,0) 的值是 5 = 5 ，为第 2 大的值。

示例 3：

输入：matrix = [[5,2],[1,6]], k = 3
输出：4
解释：坐标 (1,0) 的值是 5 XOR 1 = 4 ，为第 3 大的值。

示例 4：

输入：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] <= 106
  • 1 <= k <= m * n

Submission

运行时间: 466 ms

内存: 48.6 MB

class Solution:
    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:
        m, n = len(matrix), len(matrix[0])
        res = []
        f = [0] * (n+1)
        next_northwest = 0
        for x, line in enumerate(matrix):
            northwest = 0
            for y, v in enumerate(line):
                next_northwest = f[y+1]
                f[y+1] = matrix[x][y] ^ f[y+1] ^ f[y] ^ northwest
                northwest = next_northwest
                res.append(f[y+1])
        res.sort()
        return res[-k]

Explain

此题解采用前缀异或和的方式计算每个坐标的值。首先，它通过一个二维前缀异或和数组 f 来维护从 (0,0) 到 (i,j) 的异或结果。对于每个元素 matrix[x][y]，其对应的异或坐标值可以通过当前值与其左侧、上方和左上方的异或和来计算得到。该方法避免了重复计算，通过逐行更新，将每个坐标的值存入数组 res 中。最后，对 res 数组进行排序，并取出第 k 大的元素返回。

时间复杂度: O(mn log(mn))

空间复杂度: O(mn)

class Solution:
    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:
        m, n = len(matrix), len(matrix[0])
        res = []
        f = [0] * (n+1)  # 用于存储当前行的前缀异或结果
        next_northwest = 0  # 用于暂存左上角的异或结果
        for x, line in enumerate(matrix):
            northwest = 0  # 初始化当前行左上角的异或值
            for y, v in enumerate(line):
                next_northwest = f[y+1]  # 更新下一个左上角的异或值
                f[y+1] = matrix[x][y] ^ f[y+1] ^ f[y] ^ northwest  # 计算当前坐标的异或值
                northwest = next_northwest  # 更新 northwest 为当前的左上角值
                res.append(f[y+1])  # 将当前坐标值添加到结果列表中
        res.sort()  # 对所有坐标值进行排序
        return res[-k]  # 返回第 k 大的值

Explore

在异或运算中，任何数与0进行异或操作结果仍为该数本身。因此，矩阵中的0元素不会对异或结果产生影响，只是在计算过程中保持异或和不变。在前缀异或和数组的计算中，若当前元素为0，则该元素对异或和的影响为零，即不改变当前的异或和。因此，含有0的行或列不会对最终的计算结果产生负面影响，只是在计算过程中相当于没有增加新的影响因素。

`northwest`和`next_northwest`变量在代码中用于处理二维前缀异或和的计算。`northwest`变量存储的是当前计算位置的左上方（即西北方向）的异或和，而`next_northwest`则用于暂存下一次迭代中`northwest`的值。在每次迭代中，计算当前位置的异或值需要用到其左侧、上方和左上方的异或和。`northwest`提供了从上一行传递下来的左上方的异或和，而`next_northwest`则确保在当前行计算过程中，`northwest`值能正确地传递到下一个元素。这种机制保证了每个元素的异或计算可以正确地使用到其周围元素的前缀异或结果。

该公式的推导基于二维数组的前缀异或和的性质。在二维异或前缀和中，为了得到点 (x, y) 的异或总和，需要使用其周围三个点的前缀和：左侧的点 (x, y-1)，上方的点 (x-1, y)，以及左上方的点 (x-1, y-1)。具体来说，`matrix[x][y]` 是当前点的值；`f[y+1]` 在更新前存储的是上方点的前缀异或和；`f[y]` 存储的是左侧点的前缀异或和；`northwest` 存储的是左上方点的前缀异或和。根据异或运算的性质（自反性：a ^ a = 0），通过异或上述四个值，可以消除由于重复计算引入的重叠区域的影响，从而准确计算出点 (x, y) 的前缀异或和。这种方法利用已有的前缀和来避免冗余计算，提高了算法的效率。