1 题目描述
我们有一个由平面上的点组成的列表 points。需要从中找出 K 个距离原点 (0, 0) 最近的点。
(这里,平面上两点之间的距离是欧几里德距离。)
你可以按任何顺序返回答案。除了点坐标的顺序之外,答案确保是唯一的。
输入:points = [[1,3],[-2,2]], K = 1
输出:[[-2,2]]
解释:
(1, 3) 和原点之间的距离为 sqrt(10),
(-2, 2) 和原点之间的距离为 sqrt(8),
由于 sqrt(8) < sqrt(10),(-2, 2) 离原点更近。
我们只需要距离原点最近的 K = 1 个点,所以答案就是 [[-2,2]]。
输入:points = [[3,3],[5,-1],[-2,4]], K = 2
输出:[[3,3],[-2,4]]
(答案 [[-2,4],[3,3]] 也会被接受。)
提示
1 <= K <= points.length <= 10000
-10000 < points[i][0] < 10000
-10000 < points[i][1] < 10000
2 分析题目
topK问题,排序取前k个。
优化/简化
- 因为计算到原点的距离,所以可以这样写: sqrt(x[0]**2+x[1]**2)
- 开平方增加了计算时间,同时还失去精度,所以可以这样写 x[0]**2+x[1]**2
3 源码
3.1 优雅的python
python
def kClosest(self, points, K):
""" method1 """
# points.sort(key=lambda x: x[0] ** 2 + x[1] ** 2, reverse=False)
# return points[:K]
""" method 2"""
return sorted(points, key=lambda x: x[0] ** 2 + x[1] ** 2, reverse=False)[:K]
代码已经很清晰了,这里简单说下 sort,sorted
的区别,sort
是属于list的方法,是原地操作,sorted
返回的是一个list,适用于任何可迭代对象。
3.2 快速排序
这里可以用快速排序来解决。每次用 快排的partition
返回排序用于此轮比较元素的的下标index,这轮比较后:比这个元素大的放其后面,比其小的放前面;当index== K-1时,说明前k个元素已经满足要求;比k-1小时,去index的右边寻找,比k-1大时,去index的左边寻找。
python
def partition(self, nums, start, end):
"""
快排下标
:param nums: 待排序 list
:param start: 开始下标
:param end: 结束下标
:return: a number , index
"""
i, j = start, end
head_dist = nums[start][0] ** 2 + nums[start][1] ** 2
while True:
while i < end and nums[i][0] ** 2 + nums[i][1] ** 2 <= head_dist:
i += 1
while j > start and nums[j][0] ** 2 + nums[j][1] ** 2 > head_dist:
j -= 1
if i >= j:
break
nums[i], nums[j] = nums[j], nums[i]
nums[start], nums[j] = nums[j], nums[start]
return j
def quick_sort_k(self, nums, start, end, k):
"""
:param nums:
:param start:
:param end:
:param k:
:return:
"""
index = self.partition(nums, start, end)
if index == k - 1:
return nums[:k]
return self.quick_sort_k(nums, index + 1, end, k) if index < k - 1 else self.quick_sort_k(nums, start,
index-1, k)
3.3 优先队列
使用一个优先队列实时维护前 K 个最小的距离平方。
首先我们将前 K 个点的编号以及对应的距离平方放入优先队列中,随后从第K+1 个点开始遍历:如果当前点的距离平方比堆顶的点的距离平方要小,就把堆顶的点弹出,再插入当前的点。当遍历完成后,所有在优先队列中的点就是前 KK 个距离最小的点。
python
import heapq
q = [(-x ** 2 - y ** 2, i) for i, (x, y) in enumerate(points[:K])]
heapq.heapify(q)
n = len(points)
for i in range(K, n):
x, y = points[i]
dist = -x ** 2 - y ** 2
heapq.heappushpop(q, (dist, i))
ans = [points[identity] for (_, identity) in q]
return ans
heapq 优先队列为小根堆
4 总结
这题和剑指offer40最小的K个数几乎一摸一样,掌握快速排序、优先队列是重点,常规解法并不能使面试官满意。另外用到快排变形的题还有 “找出数组中出现次数超过一半的那个数”
原题链接: