题目描述：
我们有一个由平面上的点组成的列表points。需要从中找出K个距离原点(0,0)最近的点。（这里，平面上两点之间的距离是欧几里得距离）
你可以按任何顺序返回答案。除了点坐标的顺序之外，答案确保是唯一的。
示例1：
输入：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]]。
示例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
方法一：排序
class Solution(object):
def kClosest(self, points, K):
"""
:type points: List[List[int]]
:type K: int
:rtype: List[List[int]]
"""
points.sort(key=lambda x: (x[0]**2 + x[1]**2)**0.5)
return points[:K]
复杂度分析
- 时间复杂度：O(NlogN)，其中 N 是给定点的数量。
- 空间复杂度：O(N)。
方法二：分治法（官方解答）
思路
我们想要一个复杂度比 NlogN 更低的算法。 显然，做到这件事情的唯一办法就是利用题目中可以按照任何顺序返回 K 个点的条件，否则的话，必要的排序将会花费我们 NlogN 的时间。
我们随机地选择一个元素 x = A[i] 然后将数组分为两部分： 一部分是到原点距离小于 x 的，另一部分是到原点距离大于等于 x 的。 这个快速选择的过程与快速排序中选择一个关键元素将数组分为两部分的过程类似。
如果我们快速选择一些关键元素，那么每次就可以将问题规模缩减为原来的一半，平均下来时间复杂度就是线性的。
算法
我们定义一个函数 work(i, j, K)，它的功能是部分排序 (points[i], points[i+1], ..., points[j]) 使得最小的 K 个元素出现在数组的首部，也就是 (i, i+1, ..., i+K-1)。
首先，我们从数组中选择一个随机的元素作为关键元素，然后使用这个元素将数组分为上述的两部分。为了能使用线性时间的完成这件事，我们需要两个指针 i 与 j，然后将它们移动到放错了位置元素的地方，然后交换这些元素。
然后，我们就有了两个部分 [oi, i] 与 [i+1, oj]，其中 (oi, oj) 是原来调用 work(i, j, K) 时候 (i, j) 的值。假设第一部分有 10 个元，第二部分有15 个元素。如果 K = 5 的话，我们只需要对第一部分调用 work(oi, i, 5)。否则的话，假如说 K = 17，那么第一部分的 10 个元素应该都需要被选择，我们只需要对第二部分调用 work(i+1, oj, 7) 就行了。
自我提醒：TOP-K算法
class Solution(object):
def kClosest(self, points, K):
dist = lambda i: points[i][0]**2 + points[i][1]**2
def work(i, j, K):
if i >= j: return
oi, oj = i, j
pivot = dist(random.randint(i, j))
while i < j:
while i < j and dist(i) < pivot: i += 1
while i < j and dist(j) > pivot: j -= 1
points[i], points[j] = points[j], points[i]
if K <= i - oi + 1:
work(oi, i, K)
else:
work(i+1, oj, K - (i - oi + 1))
work(0, len(points) - 1, K)
return points[:K]
复杂度分析
- 时间复杂度：O(N) ，这是在平均情况下 的时间复杂度， 其中 N 是给定点的数量。
- 空间复杂度：O(N)。
