Jianbo Dai's

lc973.最接近原点的K个点

 
  • Jan 08, 2021

题目链接

本质是一个topK问题，所以也是既能用优先队列/堆来做，也可以用类似于快速排序的方法来做。在第一个方法中我们用python里的heapq来实现，由于python中heapq是小根堆，所以没法直接实现前K小，只能先引入负号使得堆按照坐标平方和的负数来间接完成。具体要说的也不多毕竟原理都明白，说几个点，一个是取负数；一个是用identity这样的方式类似于字典的形式（比截取列表片段更好看？）；用的heappushpop方法，比先push再pop效率高一些，和heapreplace不同的地方在于后者是先pop然后再push新的值进堆。这个算法的时间复杂度是O（NlogK），空间复杂度是O（K）。

第二个方法是快速排序的思路，时间复杂度是O（N），空间复杂度为O（logN）。

python:

import heapq
class Solution:
    def kClosest1(self, points: List[List[int]], K: int) -> List[List[int]]:
        q = [(-x **2 - y ** 2, i) for i, (x, y) in enumerate(points[:K])]
        heapq.heapify(q)

        size = len(points)
        for i in range(K, size):
            x, y = points[i]
            dist = -x **2 - y ** 2
            heapq.heappushpop(q, (dist, i))
        
        ans = [points[identity] for (_, identity) in q]
        return ans
		
    def kClosest2(self, points: List[List[int]], K: int) -> List[List[int]]:
        q = [(x**2 + y**2, i) for i, (x, y) in enumerate(points)]
        t = K
        l, r = 0, len(points)-1
        while True:
            index = self.qsort(q, l, r)
            if index == t:
                return [points[x[1]] for x in q[:t]]
            elif index > t:
                r = index - 1
            else:
                l = index + 1
    
    def qsort(self, q, left, right):
        if left >= right:
            return left
        random_index = random.randint(left, right)
        q[left], q[random_index] = q[random_index], q[left]
        i, j = left, right
        pivot = q[i]
        while i < j:
            while i < j and q[j][0] >= pivot[0]:
                j -= 1
            q[i] = q[j]
            while i < j and q[i][0] <= pivot[0]:
                i += 1
            q[j] = q[i]
        q[i] = pivot
        return i
Search