K Closest Points

Description

Given some points and a point origin in two dimensional space, find k points out of the some points which are nearest to origin.
Return these points sorted by distance, if they are same with distance, sorted by x-axis, otherwise sorted by y-axis.

Example

Given points = [[4,6],[4,7],[4,4],[2,5],[1,1]], origin = [0, 0], k = 3
return [[1,1],[2,5],[4,4]]

思考：
这个问题还蛮容易出错的。对于距离，使用 Euclidean distance, (x1-x2)**2 + (y1-y2)**2

第一种方法：
Bucket sort. 建立一个dictionary with key = distance，value = points with distance. output to sorted list. 这个蠢办法实现的复杂度很高，要以key sort dictionary然后每个bucket的成员还要再继续的sort.

第二种方法：
利用已有的函数。heapify.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

""" Definition for a point. class Point: def __init__(self, a=0, b=0): self.x = a self.y = b """ import heapq class Solution: """ @param points: a list of points @param origin: a point @param k: An integer @return: the k closest points """ def kClosest(self, points, origin, k): # write your code here pointsWithDistance = [[self.getDistance(p, origin), p.x, p.y] for p in points] heapq.heapify(pointsWithDistance) afterSort = heapq.nsmallest(k, pointsWithDistance) return [Point(p[1], p[2]) for p in afterSort] def getDistance(self, point, origin): return (point.x - origin.x)**2 + (point.y - origin.y)**2