算法练习 Leetcode 力扣 973. K Closest Points to Origin解法

feellikelearning June 16, 2020 0 Comments

典型top k 问题，主要熟悉priority queue写法。

python里面可以用heapq。时间NlogK，空间logK。

class Solution(object):
    def kClosest(self, points, K):
        """
        :type points: List[List[int]]
        :type K: int
        :rtype: List[List[int]]
        """
        pq = []
        i = 0
        for pt in points:
            record = (-self.distsq(pt), pt)
            if i < K:
                heappush(pq, record) 
                i += 1
            else:
                heappushpop(pq, record)
        ans = []
        for i in range(len(pq)):
            ans.append(heappop(pq)[1])
        return ans
            
            
    def distsq(self, point):
        return point[0]**2 + point[1]**2
        

直接sort

也行，时间NlogN，常数时间，python用lambda的话只要一行

class Solution(object):
    def kClosest(self, points, K):
        """
        :type points: List[List[int]]
        :type K: int
        :rtype: List[List[int]]
        """
        return sorted(points, key=lambda pt: pt[0]**2 + pt[1]**2)[0:K]