本文主要是介绍Leetcode 3275. K-th Nearest Obstacle Queries,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
- 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。
这篇关于Leetcode 3275. K-th Nearest Obstacle Queries的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!