- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
问题陈述如下:
Find the K closest points to the origin in a 2D plane, given an array containing N points.The output must be in non decreasing order.
解决方案:我已经使用比较器和优先级队列解决了这个问题,我的代码如下所示:
class Point {
double x;
double y;
public Point(double x, double y) {
this.x = x;
this.y = y;
}
}
public class KClosestPoints {
public Point[] getKNearestPoints(Point[] points, int k) {
if (k == 0 || points.length == 0) {
return new Point[0];
}
Point[] rValue = new Point[k];
int index = k - 1;
if (points.length < k) {
index = points.length - 1;
}
final Point org = new Point(0, 0);
PriorityQueue<Point> pq = new PriorityQueue<Point>(k,
new Comparator<Point>() {
@Override
public int compare(Point o1, Point o2) {
Double d2 = getDistance(o2, org);
Double d1 = getDistance(o1, org);
if (d2 > d1) {
return 1;
} else if (d2 < d1) {
return -1;
} else
return 0;
}
});
for (int i = 0; i < points.length; i++) {
pq.offer(points[i]);
if (pq.size() > k) {
pq.poll();
}
}
while (!pq.isEmpty()) {
rValue[index] = pq.poll();
index--;
}
return rValue;
}
private static double getDistance(Point a, Point b) {
return Math.sqrt(((a.x - b.x) * (a.x - b.x))
+ ((a.y - b.y) * (a.y - b.y)));
}
我的代码适用于我使用过的所有测试用例,除了这个:
test6[0] = new Point(Double.MIN_VALUE, Double.MAX_VALUE);
test6[1] = new Point(Double.MIN_VALUE, Double.MIN_VALUE);
test6[2] = new Point(Double.MAX_VALUE, Double.MAX_VALUE);
getKNearestPoints(test6, 2);
答案应该是 test6[0] 和 test6[1],而这段代码给出的答案是 test6[0] 和 test6[2]。帮助我找到问题所在。
编辑:后来我注意到它在所有 k = 2 的测试用例中给出了错误的答案,当点为正和负时,上面提到了一个这样的测试用例
最佳答案
你问的问题,计算距离有问题:
Point # 0 = (0, 0)
Point # 1 = (Double.MIN_VALUE, Double.MAX_VALUE) -> (4.9E-324, 1.7E308)
Point # 2 = (Double.MIN_VALUE, Double.MIN_VALUE) -> (4.9E-324, 4.9E-324)
Point # 3 = (Double.MAX_VALUE, Double.MAX_VALUE) -> (1.7E308, 1.7E308)
注意: Double.MIN_VALUE
是正数。
现在欧式距离d = Math.sqrt(((a.x - b.x) * (a.x - b.x)) + ((a.y - b.y) * (a.y - b.y)));
返回 Infinity
在计算 Point # 0
之间的距离时和 Point # 1
, 和 Point # 0
之间和 Point # 3
,因为:
第 1 点
(a.x - b.x) * (a.x - b.x) = (1.7E308 - 0) * (1.7E308 - 0) = 1.7E308 * 1.7E308 = Infinity
Math.sqrt(Infinity + Infinity) = Infinity;
得到Point # 1
的距离后和 Point # 0
( Infinity
), 然后与 Point # 3
的距离进行比较和 Point # 0
(还有 Infinity
)然后 Infinity = Infinity
是true
,因此 Comparator
表示“两点相等”,PriorityQueue
不要随意订购。
对于 Double.MAX_VALUE
的操作你不能使用 Double
,而是使用 BigDecimal
:
private BigDecimal getDistance(Point a, Point b) {
BigDecimal dx = BigDecimal.valueOf(a.x - b.x);
BigDecimal dy = BigDecimal.valueOf(a.y - b.y);
BigDecimal distance = dx.pow(2).add(dy.pow(2));
return distance;
}
为什么我们不用平方根来计算实际距离?因为:
a > b
然后sqrt(a) > sqrt(b)
,它是正比的,所以不用平方根函数就可以得到这个值。利用BigDecimal
, 它实现了自己的 Comparator
所以我们在 compareTo
中使用它Comparator
的方法定义:
@Override
public int compare(Point o1, Point o2) {
BigDecimal d1 = getDistance(o1);
BigDecimal d2 = getDistance(o2);
return d1.compareTo(d2);
}
关于java - 二维平面中的 K 最近邻,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41386490/
我有一个对象: [ { TEAMGROUP: "AB", TEAMNAME: "TEAM1", SPRINTS: [ { ID: 1,
颜色模型和颜色空间之间的差异 RGB565 与 RGB888 有何不同任何建议链接 YUV vs RGB vs YCbCr。? 最佳答案 RGB 是一种加法颜色模型,其中红色、绿色和蓝色强度以不同的组
我正在从单个顶点/索引缓冲区绘制一个具有多个网格的完整对象,并且它们具有不同的纹理。因此,我想到将纹理 ID 与顶点一起从顶点着色器传递到片段着色器中的片段。问题是禁用插值。我正在使用 GLSL ve
我有一个包含 40000 个 float 的数组,用于指定 map 上的高度级别。我想在 OpenGL ES 2.0 中创建一个网格/平面,为该网格中的每个顶点分配一个来自该数组的高度值,以便它们创建
我真的很喜欢 IQ 的页面以及有关 SDF 的信息: ( https://www.iquilezles.org/www/articles/distfunctions/distfunctions.htm
我创建了 QPushButton在带有此样式表的 Qt Designer 中: QPushButton#pushButton { background-color: #ffffff; } QP
所以我正在寻找一些平面 map 的解决方法,因为它在 IE 上不起作用,我找到了这个:但我不太明白为什么它会起作用 var gadjets = [ {computers:['asus', 'hp'
child Actor 会不会太多?例如,如果我有一个有 10000 个 child Actor 的 Actor ,与每个有 1000 个 child Actor 的 10 个 Actor 相比,这会
我有一个由法线 (n) 和距离 (d)(距原点)定义的平面。我想把它改造成一个新的系统。 长路是这样的: 1) 将距离 (d) 与法线 (n) 相乘得到一个向量 (p) 2) 旋转 (R) 并平移 (
问题: 从球体中减去立方体会得到一个结果,其中 z 轴保留体积,但 y 轴和 x 轴产生平面圆盘,如图所示。我不确定为什么球体在那些方面正在失去体积。我正在使用 threeCSG 的典型减法。 代码:
我通过 SQL 查询从我们的 ERP 获取产品数据,由此返回的数据在大小级别非常平坦。一个产品有 3 个级别: 风格 颜色 尺寸 一种款式有多种颜色,一种颜色有多种尺码。 我创建了以下模型: publ
我正在尝试展开一些 json 数据。如果我像下面这样使用我的测试数据,一切正常! var data = [ { "title": 1, "parentids": [0] }, { "title
我希望使用 SceneKit 在 Swift 中的 3D 空间中绘制多个平面。具体来说,这些表面都将位于双曲面内。我以前从未绘制过自定义形状/对象,而且在尝试理解文档时我已经迷失了方向。 关于在 3D
预先感谢您阅读我的问题。我对 ARKit 非常陌生,并且已经学习了几个教程,这些教程向我展示了如何使用平面检测以及如何为平面使用不同的纹理。这个功能真的很棒,但这是我的问题。玩家是否可以先将飞机放置在
我正在阅读下面的源代码,我想知道我到底为什么要使用平面图方式。正如我所看到的,与通过 if 语句进行简单的 null 检查相比,实例化了更多的对象,执行了更多代码,这将在第一个 null 时终止,而不
我正在编写一个 Rails 应用程序并使用 Flat UI 进行样式设置。我目前正在将 flatui-rails gem 与 twitter-bootstrap-rails gem 结合使用。一切正常
我在维基百科中找到了射线平面相交代码的解决方案,该解决方案有效,我只是在其中求解线性方程组。 后来我找到了一些点到平面投影的代码,显然实现方式不同,并且在特定条件下也会产生不同的解决方案。 但是,我并
我正在使用 http://designmodo.github.io/Flat-UI/ 中的扁平 UI 我复制了复选框示例页面中的所有文件和代码。 但是我注意到该复选框并未显示为样式复选框,但在我单击初
这个问题已经有答案了: True Isometric Projection with HTML5 Canvas (3 个回答) 已关闭 7 年前。 我想创建一个等轴测图。该 map 存在等距矩形,如图
http://designmodo.github.io/Flat-UI/ 我想创建一个 Css 下拉菜单,我已经完成了下拉部分,但是我似乎无法模拟转换,也不知道如何编写这些代码。这是我目前所知道的,在
我是一名优秀的程序员,十分优秀!