【Leetcode Daily】1738找出第K大的异或坐标值

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给一个二维数组和一个整数 k，求这个二维数组中，所有坐标的二维异或值中，第 k 大的值。

思路分享

• 曾经研究 zobristhash 时偶然了解到异或的一点性质，a^a=0，对于这里求的二维异或值，把异或看成加法就是二维前缀和。同理的，f[i][j]=f[i-1][j]^f[i][j-1]^f[i-1][j-1]+grid[i-1][j-1]

  https://leetcode.cn/problems/find-kth-largest-xor-coordinate-value/solutions/2790359/liang-chong-fang-fa-er-wei-qian-zhui-yi-689bf/

代码解答（强烈建议自行解答后再看）

• 参考题解

class Solution:
    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:
        m, n = len(matrix), len(matrix[0])
        f = [[0]*(n+1) for _ in range(m+1)]
        ans = []
        for i in range(m):
            for j in range(n):
                f[i+1][j+1] = f[i+1][j] ^ f[i][j+1] ^f[i][j] ^ matrix[i][j]
                ans.append(f[i+1][j+1])
        ans.sort()
        return ans[-k]