K closes points

此题有两种方法，一种直接写比较器然后把数组排序返回前K个就行了，这种方法时间复杂度是O(nlgn)

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
        def comparator(A, B):
            disA = (origin.y - A.y) ** 2 + (origin.x - A.x) ** 2
            disB = (origin.y - B.y) ** 2 + (origin.x - B.x) ** 2
            if disA != disB:
                return cmp(disA, disB)
            return cmp(A.x, B.x) if A.x != B.x else cmp(A.y, B.y)

        points.sort(cmp=comparator)

        return points[:k]

当然就也可以用堆了，但是这里用堆需要注意题目根据坐标定大小的要求，我们需要自己自定义一个类同时构造这个类的比较器才能最后传入堆进行排序，时间复杂度就是O(nlgk)，不过需要注意这里的比较顺序，因为要找的是最近的K个点，实际上我们构造的是一个最大堆

import heapq

class Type:
    def __init__(self, distance, point):
        self.distance = distance
        self.point = point

    def __cmp__(self, other):
        if self.distance != other.distance:
            return cmp(other.distance, self.distance)
        return cmp(other.point.x, self.point.x) if self.point.x != other.point.x else cmp(other.point.y, self.point.y)

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
        heap = []
        n = len(points)
        for i in xrange(n):
            distance = (origin.y - points[i].y) ** 2 + (origin.x - points[i].x) ** 2
            heapq.heappush(heap, Type(distance, points[i]))
            if i >= k:
                heapq.heappop(heap)

        result = []
        while heap:
            result.append(heapq.heappop(heap).point)
        return result[::-1]