找出所有离原点最近的k点
找出所有离原点最近的k点
提问于 2019-04-28 05:44:57
我们有一张飞机上的要点清单。找到离原点最近的K点(0，0)。(在这里，平面上两点之间的距离是欧几里德距离。)你可以按任何顺序返回答案。答案保证是唯一的(除了它的顺序)。例1:输入: points = [1,3，-2,2]，K=1 Output：[-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]注释：
- 1 <= K <= points.length <= 10000
- -10000 <我< 10000
- -10000 <我< 10000
还请注意，可能存在两个节点的距离相等的情况，因此可以打印任何节点。
这是我的方法。
- 取树图(这样我就可以得到所有的排序距离)
- 开始填充所有点的树状图
- 最后取第一个k元。
public class KClosestPointsToOrigin {
public int[][] kClosest(int[][] points, int K) {
int rows = points.length;
SortedMap<Double, List<CoordinatePoint>> distanceToPoint = new TreeMap<>();
for(int i =0; i<rows; i++) {
double distance = getDistance(points[i]);
if(Objects.nonNull(distanceToPoint.get(distance))) {
List<CoordinatePoint> coordinatePointList = distanceToPoint.get(distance);
coordinatePointList.add(new CoordinatePoint(points[i][0], points[i][1]));
} else {
List<CoordinatePoint> coordinatePoints = new ArrayList<>();
coordinatePoints.add(new CoordinatePoint(points[i][0], points[i][1]));
distanceToPoint.put(distance, coordinatePoints);// x and y coordinates.
}
}
int[][] arrayToReturn = new int[K][2];
int counter = 0;
for (Double key : distanceToPoint.keySet()) {
List<CoordinatePoint> coordinatePoints = distanceToPoint.get(key);
Iterator iterator1 = coordinatePoints.iterator();
while (iterator1.hasNext() && counter < K) {
CoordinatePoint coordinatePoint = (CoordinatePoint) iterator1.next();
arrayToReturn[counter][0] = coordinatePoint.x;
arrayToReturn[counter][1] = coordinatePoint.y;
counter++;
}
}
return arrayToReturn;
}
private double getDistance(int[] point) {
int x = point[0];
int y = point[1];
int x2 = Math.abs(x) * Math.abs(x);
int y2 = Math.abs(y) * Math.abs(y);
return Math.sqrt(x2+y2);
}
}
class CoordinatePoint {
int x;
int y;
public CoordinatePoint(int x, int y) {
this.x = x;
this.y = y;
}
}但是，由于运行时和内存使用率很高，此解决方案并不有效。你能帮我优化解决方案吗。
回答 1
Code Review用户
发布于 2019-04-28 07:43:58
这个任务听起来像是直接来自Java 8流API的广告：
- 按距离对点进行排序
- 取最小k点
这归结为以下代码：
static int[][] kClosest(int[][] points, int k) {
return Arrays.stream(points)
.sorted(Comparator.comparing((int[] point) -> point[0] * point[0] + point[1] * point[1]))
.limit(k)
.toArray(int[][]::new);
}那代码是从我头上写的。由于Java是通用的，并且打算进行高度优化，它应该注意到它只需要记住k最小的元素。您应该通过计算调用距离函数的频率来检查这一点。要做到这一点，您应该将其提取到本地方法，这是IDE可以为您做的事情。
与您的代码相比：
- 我省略了
Math.sqrt，因为点坐标被限制在10000，这意味着距离的平方最多可以变为2e8，幸运的是它比Integer.MAX_VALUE小一些。 - 调用
Math.abs也是不必要的。 - 当给定的点都有相同的距离时，制作一张列表图可能有助于病理病例。在其他情况下，它可以被排除在外。
页面原文内容由Code Review提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://codereview.stackexchange.com/questions/219291
复制相关文章
相似问题
腾讯云开发者
