题目
找出第k大的异或坐标值
给你一个二维矩阵
matrix和一个整数k，矩阵大小为m x n由非负整数组成。
矩阵中坐标
(a, b)的 值 可由对所有满足0 <= i <= a < m且0 <= j <= b < n的元素matrix[i][j]（下标从0开始计数）执行异或运算得到。
请你找出
matrix的所有坐标中第k大的值（k的值从1开始计数）。
解法
class Solution:
def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:
width = len(matrix[0])
results = [0] * width
for line in matrix:
res = self.traverseXOR(line)
for i in range(width):
results.append(next(res) ^ results[-width])
results.sort()
return results[-k]
def traverseXOR(self, line: List[int]) -> int:
res = 0
for element in line:
res ^= element
yield res心路历程
第一次
用for循环遍历坐标, 又对每个坐标遍历其值所需的元素, 并将其格式化为字符串存入列表, 使用字符串的join方法配合eval函数, 计算坐标值并存入列表中, 最终对列表升序排序并用-k作为索引取第k大的值.
第38/49个测试用例超时.
第二次
怀疑是列表的存取效率太低, 将字符串join用于异或运算的方法改为迭代求取每个坐标的值.
第40/49个测试用例超时.
第三次
意识到计算重复度过高, 其实每个坐标值的运算可以直接用先前的(即上方坐标值和左侧坐标值)求得. 将矩阵以行为单位, 每行用生成器运算该行内的运算结果. 将运算结果与上侧坐标值求异或, 即可得到该坐标右侧的坐标值, 存入列表.
测试成功, 执行用时752ms.
