记第一次力扣刷题

题目

找出第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.
$}YK(IGM%KJ(F8K~`)HBE$H.png

tag(s): python
show comments · back · home
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。知识共享许可协议
Say something...