973. K Closest Points to Origin

Loading...LeetCode

1 <= K <= points.length <= 10000

O(n**2) 肯定TLE，只能考虑 O(n) 或者 O(n*logn) 的算法了。只遍历一次的话是可以基于O(n)的，只是需要一直维护结果数组，而且要返回的是坐标而非距离，那就要同时维护两套值，写起来绕了点，但不算复杂。

class Solution:
    def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
        if not points: return []
        
        res, dis = [], []
        far = (0, 0)
        
        for x, y in points:
            if len(res) < K:
                res.append([x,y])
                dis.append(x**2+y**2)
                far = (dis.index(max(dis)), max(dis))
            elif len(res) >= K and x**2+y**2 < far[1]:
                del res[far[0]]
                del dis[far[0]]
                res.append([x,y])
                dis.append(x**2+y**2)
                far = (dis.index(max(dis)), max(dis))            
        return res

提交后发现这个还是特别慢，忽然意识到可以明明可以直接sort...一行搞定。

class Solution(object):
    def kClosest(self, points, K):
        return sorted(points, key = lambda cord: cord[0]**2+cord[1]**2)[:K]