973-最接近原点的 K 个点

前言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<Double,int[]> map=new TreeMap<>(); for (int i=0;i<points.length;i++){ int x=points[i][0]; int y=points[i][1]; //某个点到原点的欧几里德距离为坐标值的平方之和开根号即可 double distance=Math.sqrt(Math.pow(x,2)+Math.pow(y,2)); map.put(distance,points[i]); } int[][] result=new int[K][2]; Iterator<Map.Entry<Double,int[]>> 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; }