- Leetcode 3275. K-th Nearest Obstacle Queries
- 1. 解题思路
- 2. 代码实现
- 题目链接：3275. K-th Nearest Obstacle Queries
1. 解题思路
这一题的话其实逻辑上非常简单，就是维护一个距离的有序数组，不断取第k大的元素即可。
不过好死不死的题目设置成只要这么干就一定超时，因此我们不得不想办法去优化算法复杂度，但说白了其实也就是换用堆排，实在是不明白出题人脑子里面想的是啥……
2. 代码实现
给出python代码实现如下：
class Solution:def resultsArray(self, queries: List[List[int]], k: int) -> List[int]:ans = [-1 for _ in queries]if len(queries) < k:return ansdistances = [-abs(x)-abs(y) for x, y in queries[:k]]heapq.heapify(distances)ans[k-1] = -distances[0]for i, (x, y) in enumerate(queries[k:]):d = abs(x) + abs(y)if d < -distances[0]:heapq.heappush(distances, -d)heapq.heappop(distances)ans[i+k] = -distances[0]return ans
提交代码评测得到：耗时2725ms，占用内存110.5MB。