Problem
Given some points and a point origin in two dimensional space, find k points out of the some points which are nearest to origin.
Return these points sorted by distance, if they are same with distance, sorted by x-axis, otherwise sorted by y-axis.
Given points = [[4,6],[4,7],[4,4],[2,5],[1,1]], origin = [0, 0], k = 3
return [[1,1],[2,5],[4,4]]
/** * Definition for a point. * class Point { * int x; * int y; * Point() { x = 0; y = 0; } * Point(int a, int b) { x = a; y = b; } * } */ public class Solution { /* * @param points: a list of points * @param origin: a point * @param k: An integer * @return: the k closest points */ public Point[] kClosest(Point[] points, Point origin, int k) { ComparatorpointComparator = new Comparator () { public int compare(Point A, Point B) { if (distance(B, origin) == distance(A, origin)) { if (A.x == B.x) { return A.y - B.y; } else { return A.x - B.x; } } else { //maintain a min heap return distance(A, origin) > distance(B, origin) ? 1 : -1; } } }; PriorityQueue Q = new PriorityQueue (k, pointComparator); for (Point point: points) { Q.add(point); } Point[] res = new Point[k]; for (int i = 0; i < k; i++) { res[i] = Q.poll(); } return res; } public double distance(Point A, Point B) { int l = Math.abs(A.x - B.x); int w = Math.abs(A.y - B.y); return Math.sqrt(Math.pow(l, 2) + Math.pow(w, 2)); } }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/68189.html
摘要:题目链接题目分析给一个坐标数组,从中返回个离最近的坐标。其中,用欧几里得距离计算。思路把距离作为数组的键,把对应坐标作为数组的值。用函数排序,再用函数获取前个即可。最终代码若觉得本文章对你有用,欢迎用爱发电资助。 973. K Closest Points to Origin 题目链接 973. K Closest Points to Origin 题目分析 给一个坐标数组points...
摘要:这个题和的做法基本一样,只要在循环内计算和最接近的和,并赋值更新返回值即可。 Problem Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three intege...
摘要:两次循环对中第个和第个进行比较设置重复点数,相同斜率点数。内部循环每次结束后更新和点相同斜率的点的最大数目。外部循环每次更新为之前结果和本次循环所得的较大值。重点一以一个点为参照求其他点连线的斜率,不需要计算斜率。 Problem Given n points on a 2D plane, find the maximum number of points that lie on th...
Problem Youre now a baseball game point recorder. Given a list of strings, each string can be one of the 4 following types: Integer (one rounds score): Directly represents the number of points you get...
阅读 2125·2021-11-15 11:36
阅读 1409·2021-09-23 11:55
阅读 2466·2021-09-22 15:16
阅读 1997·2019-08-30 15:45
阅读 1812·2019-08-29 11:10
阅读 981·2019-08-26 13:40
阅读 890·2019-08-26 10:44
阅读 3135·2019-08-23 14:55