k-closest-points(K个最接近的点|k-closest-points(K个最接近的点 )PriorityQueue
描述
给定一些 points 和一个 origin,从 points 中找到 k 个离 origin 最近的点。按照距离由小到大返回。如果两个点有相同距离,则按照x值来排序;若x值也相同,就再按照y值排序。
心得
【k-closest-points(K个最接近的点|k-closest-points(K个最接近的点 )PriorityQueue】复习了comparator的重写,与Arrays.sort()差不多,重写comparator的compare函数,可以实现自定义排序。升序前减后,降序后减前。
代码
* class Point {
*int x;
*int y;
*Point() { x = 0;
y = 0;
}
*Point(int a, int b) { x = a;
y = b;
}
* }
*/
class Pair {
int x,y,d;
Pair(int x, int y, int d) {
this.x = x;
this.y = y;
this.d = d;
}
}public class Solution {
/**
* @param points: a list of points
* @param origin: a point
* @param k: An integer
* @return: the k closest points
*/
public int distance(Point point, Point origin) {
int x = point.x - origin.x;
int y = point.y - origin.y;
int result = x*x+y*y;
return result;
}
public Point[] kClosest(Point[] points, Point origin, int k) {
// write your code here
Pair[] p = new Pair[points.length];
Point[] result5 = new Point[k];
for(int i = 0;
i < points.length;
i++) {
Pair tmp9 = new Pair(points[i].x,points[i].y,distance(points[i], origin));
p[i] = tmp9;
}
PriorityQueue queue = new PriorityQueue(k,new Comparator(){
@Override//重写compare函数
public int compare(Pair a, Pair b) {
if(a.d == b.d) {
if(a.x == b.x) {
return a.y - b.y;
}
else {
return a.x - b.x;
}
}
else {
return a.d - b.d;
}
}
});
for(int i =0;
i < p.length;
i++) {
queue.offer(p[i]);
}
for(int i = 0;
i < k;
i++) {
Pair tmp = queue.poll();
Point tmp2 = new Point(tmp.x,tmp.y);
result5[i] = tmp2;
}
return result5;
}
}
推荐阅读
- JAVA(抽象类与接口的区别&重载与重写&内存泄漏)
- 基于微信小程序带后端ssm接口小区物业管理平台设计
- 2020-04-07vue中Axios的封装和API接口的管理
- 画解算法(1.|画解算法:1. 两数之和)
- 标签、语法规范、内联框架、超链接、CSS的编写位置、CSS语法、开发工具、块和内联、常用选择器、后代元素选择器、伪类、伪元素。
- 宋仲基&宋慧乔(我们不公布恋情,我们直接结婚。)
- 考前焦虑——接纳情绪,转移注意力
- 调取接口时报404错误(ID:16)
- Hive常见问题汇总
- CICC(脑机接口,科幻几近成真())