973-最接近原点的 K 个点

li21 发布于2019-08-16 14:24 / 1687人阅读

摘要：前言的最接近原点的个点我们有一个由平面上的点组成的列表。这里，平面上两点之间的距离是欧几里德距离。提示解题思路本题首先要知道什么是欧几里德距离。欧几里德距离又叫做欧几里德度量，指的是是欧几里得空间中两点间普通即直线距离。

前言

Weekly Contest 119的最接近原点的 K 个点：

我们有一个由平面上的点组成的列表 points。需要从中找出 K 个距离原点 (0, 0) 最近的点。
（这里，平面上两点之间的距离是欧几里德距离。）
你可以按任何顺序返回答案。除了点坐标的顺序之外，答案确保是唯一的。
示例1：
输入：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]]。
示例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][3] < 10000

解题思路

本题首先要知道什么是欧几里德距离。欧几里德距离又叫做欧几里德度量，指的是是欧几里得空间中两点间“普通”（即直线）距离。只是说概念大家很难理解，先用本题需要用到的二维空间中计算欧几里德距离的数学公式就能很好理解了：
已知原点坐标为(0,0)，存在两个点A(x1,y1)和B(x2,y2)，则点A和B的欧几里德距离则为

$$ sqrt{(x_1-x_2)^2+(y_1-y_2)^2} $$

而点A到原点的欧几里德距离则为

$$ sqrt{x_1^2+y_1^2} $$

然后利用这个公式可以计算出每个点到原点的欧几里德距离，之后只需要找出最近的几个点即可。
此处需要注意题目中的

除了点坐标的顺序之外，答案确保是唯一的

这说明每个点到原点的举例应该都是不同的。

实现代码

    /**
     * 973. 最接近原点的 K 个点
     * 某个点到原点的欧几里德距离为坐标值的平方之和开根号即可
     * @param points
     * @param K
     * @return
     */
    public int[][] kClosest(int[][] points, int K) {
        //根据题目意思，每个点到原点的欧几里德距离都不同，可以用距离作为key
        //Map选择TreeMap是因为TreeMap的key是有序（从小到大）
        Map map=new TreeMap<>();
        for (int i=0;i> it=map.entrySet().iterator();
        //当前遍历到第几个元素，用于控制点的个数
        int index=0;
        while (it.hasNext()){
            int[] point=it.next().getValue();
            result[index]=point;
            if(index+1==K){
                break;
            }else{
                ++index;
            }
        }
        return result;
    }

云服务器 GPU云服务器最接近点对算法代码原点互联最便宜阿里云服务器开票几个点电信云服务器租赁专票几个点

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/72982.html

Leetcode PHP题解--D29 973. K Closest Points to Origi

摘要：题目链接题目分析给一个坐标数组，从中返回个离最近的坐标。其中，用欧几里得距离计算。思路把距离作为数组的键，把对应坐标作为数组的值。用函数排序，再用函数获取前个即可。最终代码若觉得本文章对你有用，欢迎用爱发电资助。 973. K Closest Points to Origin 题目链接 973. K Closest Points to Origin 题目分析给一个坐标数组points...

Sanchi 2019-07-01 12:39 评论0 收藏0
机器学习——K近邻算法

摘要：而代码是给出现情况增加次数，出现一次排序导入运算符模块的方法，按照第二个元素的次序对元组进行排序，此处的排序为逆序。机器学习——K近邻算法概述 k近邻是一种基本分类与回归方法. 输入:特征向量输出:实例的类别(可取多类) 核心思想:如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特性. 优点:计算精度高、对异常值...

SexySix 2019-07-30 16:24 评论0 收藏0