題目描述：

我們有一個由平面上的點組成的列表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]

復(fù)雜度分析

• 時間復(fù)雜度：O(NlogN)，其中 N 是給定點的數(shù)量。
• 空間復(fù)雜度：O(N)。

方法二：分治法（官方解答）

思路

我們想要一個復(fù)雜度比 NlogN 更低的算法。 顯然，做到這件事情的唯一辦法就是利用題目中可以按照任何順序返回 K 個點的條件，否則的話，必要的排序?qū)ㄙM我們 NlogN 的時間。

我們隨機地選擇一個元素 x = A[i] 然后將數(shù)組分為兩部分： 一部分是到原點距離小于 x 的，另一部分是到原點距離大于等于 x 的。 這個快速選擇的過程與快速排序中選擇一個關(guān)鍵元素將數(shù)組分為兩部分的過程類似。

如果我們快速選擇一些關(guān)鍵元素，那么每次就可以將問題規(guī)?？s減為原來的一半，平均下來時間復(fù)雜度就是線性的。

算法

我們定義一個函數(shù) work(i, j, K)，它的功能是部分排序 (points[i], points[i+1], ..., points[j]) 使得最小的 K 個元素出現(xiàn)在數(shù)組的首部，也就是 (i, i+1, ..., i+K-1)。

首先，我們從數(shù)組中選擇一個隨機的元素作為關(guān)鍵元素，然后使用這個元素將數(shù)組分為上述的兩部分。為了能使用線性時間的完成這件事，我們需要兩個指針 i 與 j，然后將它們移動到放錯了位置元素的地方，然后交換這些元素。

然后，我們就有了兩個部分 [oi, i] 與 [i+1, oj]，其中 (oi, oj) 是原來調(diào)用 work(i, j, K) 時候 (i, j) 的值。假設(shè)第一部分有 10 個元，第二部分有15 個元素。如果 K = 5 的話，我們只需要對第一部分調(diào)用 work(oi, i, 5)。否則的話，假如說 K = 17，那么第一部分的 10 個元素應(yīng)該都需要被選擇，我們只需要對第二部分調(diào)用 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]

復(fù)雜度分析

• 時間復(fù)雜度：O(N) ，這是在平均情況下 的時間復(fù)雜度， 其中 N 是給定點的數(shù)量。
• 空間復(fù)雜度：O(N)。