daily-leetCode-2020-1109-973-最接近原点的k个点


1 题目描述

我们有一个由平面上的点组成的列表 points。需要从中找出 K 个距离原点 (0, 0) 最近的点。

(这里,平面上两点之间的距离是欧几里德距离。)

你可以按任何顺序返回答案。除了点坐标的顺序之外,答案确保是唯一的。

输入:points = [[1,3],[-2,2]], K = 1
输出:[[-2,2]]
解释: 
(1, 3) 和原点之间的距离为 sqrt(10),
(-2, 2) 和原点之间的距离为 sqrt(8),
由于 sqrt(8) < sqrt(10),(-2, 2) 离原点更近。
我们只需要距离原点最近的 K = 1 个点,所以答案就是 [[-2,2]]。


输入:points = [[3,3],[5,-1],[-2,4]], K = 2
输出:[[3,3],[-2,4]]
(答案 [[-2,4],[3,3]] 也会被接受。)


提示
1 <= K <= points.length <= 10000
-10000 < points[i][0] < 10000
-10000 < points[i][1] < 10000

2 分析题目

topK问题,排序取前k个。

优化/简化

  1. 因为计算到原点的距离,所以可以这样写: sqrt(x[0]**2+x[1]**2)
  2. 开平方增加了计算时间,同时还失去精度,所以可以这样写 x[0]**2+x[1]**2

3 源码

3.1 优雅的python

python
    def kClosest(self, points, K):

        """ method1 """
        # points.sort(key=lambda x: x[0] ** 2 + x[1] ** 2, reverse=False)
        # return points[:K]

        """ method 2"""
        return sorted(points, key=lambda x: x[0] ** 2 + x[1] ** 2, reverse=False)[:K]

代码已经很清晰了,这里简单说下 sort,sorted的区别,sort是属于list的方法,是原地操作,sorted返回的是一个list,适用于任何可迭代对象。

3.2 快速排序

这里可以用快速排序来解决。每次用 快排的partition返回排序用于此轮比较元素的的下标index,这轮比较后:比这个元素大的放其后面,比其小的放前面;当index== K-1时,说明前k个元素已经满足要求;比k-1小时,去index的右边寻找,比k-1大时,去index的左边寻找。

python
    def partition(self, nums, start, end):
        """

        快排下标
        :param nums:  待排序 list
        :param start:  开始下标
        :param end:  结束下标
        :return:  a number , index
        """

        i, j = start, end
        head_dist = nums[start][0] ** 2 + nums[start][1] ** 2
        while True:

            while i < end and nums[i][0] ** 2 + nums[i][1] ** 2 <= head_dist:
                i += 1
            while j > start and nums[j][0] ** 2 + nums[j][1] ** 2 > head_dist:
                j -= 1
            if i >= j:
                break
            nums[i], nums[j] = nums[j], nums[i]

        nums[start], nums[j] = nums[j], nums[start]
        return j

    def quick_sort_k(self, nums, start, end, k):
        """


        :param nums:
        :param start:
        :param end:
        :param k:
        :return:
        """
        index = self.partition(nums, start, end)

        if index == k - 1:
            return nums[:k]
        return self.quick_sort_k(nums, index + 1, end, k) if index < k - 1 else self.quick_sort_k(nums, start,
                                                                                                  index-1, k)

3.3 优先队列

使用一个优先队列实时维护前 K 个最小的距离平方。

首先我们将前 K 个点的编号以及对应的距离平方放入优先队列中,随后从第K+1 个点开始遍历:如果当前点的距离平方比堆顶的点的距离平方要小,就把堆顶的点弹出,再插入当前的点。当遍历完成后,所有在优先队列中的点就是前 KK 个距离最小的点。

python
        import heapq

        q = [(-x ** 2 - y ** 2, i) for i, (x, y) in enumerate(points[:K])]
        heapq.heapify(q)

        n = len(points)
        for i in range(K, n):
            x, y = points[i]
            dist = -x ** 2 - y ** 2
            heapq.heappushpop(q, (dist, i))

        ans = [points[identity] for (_, identity) in q]
        return ans

heapq 优先队列为小根堆

4 总结

这题和剑指offer40最小的K个数几乎一摸一样,掌握快速排序、优先队列是重点,常规解法并不能使面试官满意。另外用到快排变形的题还有 “找出数组中出现次数超过一半的那个数”

原题链接:

973. 最接近原点的 K 个点


作者: jdi146
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 jdi146 !
评论

Gitalking ...

评论
Powered By Valine
v1.4.14