题目描述
给定一些 points 和一个 origin，从 points 中找到 k 个离 origin 最近的点。按照距离由小到大返回。如果两个点有相同距离，则按照x值来排序；若x值也相同，就再按照y值排序。
测试样例
输入: points = [[4,6],[4,7],[4,4],[2,5],[1,1]], origin = [0, 0], k = 3
输出: [[1,1],[2,5],[4,4]]
输入: points = [[0,0],[0,9]], origin = [3, 1], k = 1
输出: [[0,0]]
解题思路
首先加个说明，输入参数的points是由Point()对象组成的list，而origin本身就是一个Point()对象，Point()对象的class定义如下：
"""
Definition for a point.
class Point:
def __init__(self, a=0, b=0):
self.x = a
self.y = b
"""
这题解法很多..如果从代码实现的维度来看，真的是多到眼花缭乱，有些甚至一行代码就KO掉了。然而从思想本质上来看，通常是以下3种：
1、堆
时间复杂度 -- O(nlogk)O(nlogk)
最大堆或最小堆都行，只要能按题目要求将顺序对应上。
将每个点转换为对应三元组：（距离, x, y）并加入堆中，在堆中这些元组会按照 距离> x > y的优先级进行排序。在加入堆的过程中，我们可以让序列长度始终不大于k，若超出了k，则将优先级最低的元素弹出。最后，我们将堆中的元素按题目要求的次序取出并重新依次构建出各个Point()对象组成的序列即可。
2、Quick Select
时间复杂度 -- O(n+klogk)
类似于Quick Sort，先计算所有点到原点的距离，构造三元组序列，类似方法1；然后将序列中优先级最高的k个点排在前面（注意它们之间并未排序）；接着取出序列中的前k个进行排序；最后根据对应顺序重新构造Point()对象组成的序列返回。
重点在于如何将优先级最高的k个点排在前面。
我们可以先确定一个挑选元素的范围，起始是整个序列，l=0, r=len(seq) - 1，当l<r一直重复select过程。这期间如果返回的位置m == k-1，代表0~k-1这k个位置是序列中优先级最高的k个元素，那么可以结束select过程；否则，若返回的位置m > k-1,则我们要进一步缩减挑选的范围，令r = m - 1；否则令l = m + 1。
那么具体又是如何select的呢？
每次select都有对应的范围l~r，以r位置的元素作为对比，同时设定一个标记位置i（从l-1开始），让l~r-1位置的元素与其比较优先级，若某个位置j对应的元素较优，则i加一，并将这个元素与位置i的元素交换位置，这样一直重复下去..最后还要记得将i加多一次1，令r位置的元素与i位置的元素对调。
3、距离哈希法
设置一个dict，key是距离，value是list，包含各个与原点距离相同的点的横、纵坐标元组。
遍历所有点，将结果设置到dict，然后将dict的key即距离进行排序，取出对应的list，并将list也进行排序，优先级是x>y，然后构造对应的Point()对象加入到最终要返回的list中。
代码
1、堆
"""
Definition for a point.
class Point:
def __init__(self, a=0, b=0):
self.x = a
self.y = b
"""
import heapq
class Solution:
"""
@param points: a list of points
@param origin: a point
@param k: An integer
@return: the k closest points
"""
def kClosest(self, points, origin, k):
q = []
for p in points:
# heapq默认是最大堆的形式，因此取反
heapq.heappush(q, (-(p.x - origin.x) ** 2 - (p.y - origin.y) ** 2, -p.x, -p.y))
# 保持堆的长度不超过k,
# 若超出则弹出优先级最低的
if len(q) > k:
heapq.heappop(q)
# 这里的nlargest是对负数而言，反过来就代表正数的最小值
return [Point(-x, -y) for _, x, y in heapq.nlargest(k, q)]
2、Quick Select
"""
Definition for a point.
class Point:
def __init__(self, a=0, b=0):
self.x = a
self.y = b
"""
class Solution:
"""
@param points: a list of points
@param origin: a point
@param k: An integer
@return: the k closest points
"""
def kClosest(self, points, origin, k):
# 三元组序列：与原点的L2距离、横、纵坐标
dis = [((p.x - origin.x) ** 2 + (p.y - origin.y) ** 2, p.x, p.y) for p in points]
# 将序列中较小的k个点排在前面（k个点之间未排序）
self._quick_select(dis, k)
# 选择前k个并且相互之间进行排序
closest_k = sorted(dis[:k])
return [Point(x, y) for _, x, y in closest_k]
def _quick_select(self, seq, k):
l, r = 0, len(seq) - 1
while l < r:
# 返回的位置m代表0~m这些位置上的值是序列中较小的
# 但它们之间相互还未进行排序
m = self._helper(seq, l, r)
if m == k - 1:
break
elif m < k - 1:
l = m + 1
else:
r = m - 1
def _helper(self, seq, l, r):
# 以r位置上的元素作为对比
cmp_dis, cmp_x, cmp_y = seq[r]
i = l - 1
for j in range(l, r):
cur_dis, cur_x, cur_y = seq[j]
if cur_dis < cmp_dis or (cur_dis == cmp_dis and cur_x < cmp_x) or (cur_dis == cmp_dis and cur_x == cmp_x and cur_y < cmp_y):
# 每次都将小于对比元素的元素排在前面
i += 1
seq[i], seq[j] = seq[j], seq[i]
i += 1
seq[i], seq[r] = seq[r], seq[i]
return i
3、距离哈希法
"""
Definition for a point.
class Point:
def __init__(self, a=0, b=0):
self.x = a
self.y = b
"""
from collections import defaultdict
class Solution:
"""
@param points: a list of points
@param origin: a point
@param k: An integer
@return: the k closest points
"""
def kClosest(self, points, origin, k):
distance = defaultdict(list)
for p in points:
d = (p.x - origin.x) ** 2 + (p.y - origin.y) ** 2
distance[d].append((p.x, p.y))
ans = []
for d in sorted(distance.keys()):
for x, y in sorted(distance[d]):
ans.append(Point(x, y))
if len(ans) == k:
return ans
网友评论