[D&Q] - 973. K Closest Points to Origin

We have a list of points on the plane.  Find the K closest points to the origin (0, 0).

(Here, the distance between two points on a plane is the Euclidean distance.)

You may return the answer in any order.  The answer is guaranteed to be unique (except for the order that it is in.)

 

Example 1:

Input: points = [[1,3],[-2,2]], K = 1 Output: [[-2,2]] Explanation: The distance between (1, 3) and the origin is sqrt(10). The distance between (-2, 2) and the origin is sqrt(8). Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin. We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]].

Example 2:

Input: points = [[3,3],[5,-1],[-2,4]], K = 2 Output: [[3,3],[-2,4]] (The answer [[-2,4],[3,3]] would also be accepted.)

 

heapify를 써서 Sorting을 빨리 해준다. O(n^2) -> O(nlogn)

 

그래서 Divide and Conquer 인거 같다.

 

Heap이라는게 child가 2개가 있긴 때문에 그러지않을까 라는 생각이 든다.

 

Heap에 대해서 정리를 해보자면

 

https://docs.python.org/2/library/heapq.html

8.4. heapq — Heap queue algorithm — Python 2.7.17rc1 documentation

 

https://www.geeksforgeeks.org/heap-queue-or-heapq-in-python/