資訊專欄INFORMATION COLUMN
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) {
Comparator pointComparator = 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));
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/68189.html
摘要：題目鏈接題目分析給一個(gè)坐標(biāo)數(shù)組，從中返回個(gè)離最近的坐標(biāo)。其中，用歐幾里得距離計(jì)算。思路把距離作為數(shù)組的鍵，把對(duì)應(yīng)坐標(biāo)作為數(shù)組的值。用函數(shù)排序，再用函數(shù)獲取前個(gè)即可。最終代碼若覺得本文章對(duì)你有用，歡迎用愛發(fā)電資助。 973. K Closest Points to Origin 題目鏈接 973. K Closest Points to Origin 題目分析 給一個(gè)坐標(biāo)數(shù)組points...
摘要：這個(gè)題和的做法基本一樣，只要在循環(huán)內(nèi)計(jì)算和最接近的和，并賦值更新返回值即可。 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...
摘要：兩次循環(huán)對(duì)中第個(gè)和第個(gè)進(jìn)行比較設(shè)置重復(fù)點(diǎn)數(shù)，相同斜率點(diǎn)數(shù)。內(nèi)部循環(huán)每次結(jié)束后更新和點(diǎn)相同斜率的點(diǎn)的最大數(shù)目。外部循環(huán)每次更新為之前結(jié)果和本次循環(huán)所得的較大值。重點(diǎn)一以一個(gè)點(diǎn)為參照求其他點(diǎn)連線的斜率，不需要計(jì)算斜率。 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...
閱讀 2165·2021-11-15 11:36
閱讀 1506·2021-09-23 11:55
閱讀 2498·2021-09-22 15:16
閱讀 2036·2019-08-30 15:45
閱讀 1872·2019-08-29 11:10
閱讀 1037·2019-08-26 13:40
閱讀 925·2019-08-26 10:44
閱讀 3179·2019-08-23 14:55
