973-最接近原点的 K 个点

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

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

前言

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;
    }

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

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

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

机器学习-01-K-临近算法学习

摘要：算法又叫算法，这个算法是机器学习里面一个比较经典的算法，总体来说算法是相对比较容易理解的算法。其中的表示最接近自己的个数据样本。我们可以看到，机器学习的本质是基于一种数据统计的方法相关算法链接理解矩阵乘法 K Nearest Neighbor算法又叫KNN算法，这个算法是机器学习里面一个比较经典的算法，总体来说KNN算法是相对比较容易理解的算法。其中的K表示最接近自己的K个数据样本。...

fredshare 2019-06-26 15:31 评论0 收藏0
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
GPU 渲染管线与着色器大白话总结 ---- 一篇就够

摘要：它的处理单位是顶点，也就是每个顶点，都会调用一次顶点着色器。这里给一个的代码，把顶点着色器和片元着色器的代码，放到了一个文件中，不过引擎会解析文件，转换个着色器代码段，传递给。通常，顶点着色器只处理顶点坐标，进行空间转换。 ...

roadtogeek 2021-10-13 09:40 评论0 收藏0
Annoy搜索算法(Approximate Nearest Neighbors Oh Yeah)

摘要：对应的二叉树结构如下所示通过上述步骤，我们建立了二叉树的结构用于表示上述点分布空间，每个节点都表示一个子空间，在点分布空间中接近的子空间在二叉树结构中表现为位置靠近的节点。如果要搜索空间中的任意一个点，我们都可以从根结点遍历二叉树。 showImg(https://segmentfault.com/img/bV5HCC?w=1024&h=793); annoy 算法的目标是建立一个数据...

Shonim 2019-05-28 18:40 评论0 收藏0
机器学习——K近邻算法

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

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