java – 查找(x,y)坐标之间的最大距离

发布时间：2020-12-14 23:32:11 所属栏目：Java 来源：网络整理

导读：我试图计算一个大的2D输入的最大曼哈顿距离,输入由(x,y)s组成,我想要做的是计算这些坐标之间的最大距离小于O(n ^ 2)时间,我可以通过遍历所有元素来在O(n ^ 2)中完成它,例如： *(两点(X1,Y1)和(X2,Y2)之间的曼哈顿距离为：| X1-X2 | | Y1-Y2 |) for ( 0 - n )

我试图计算一个大的2D输入的最大曼哈顿距离,输入由(x,y)s组成,我想要做的是计算这些坐标之间的最大距离小于O(n ^ 2)时间,我可以通过遍历所有元素来在O(n ^ 2)中完成它,例如：
*(两点(X1,Y1)和(X2,Y2)之间的曼哈顿距离为：| X1-X2 | | Y1-Y2 |)

for ( 0 -> n )  
   for ( 0-> n )   
       { // here i calculate |Xi - Xj| + |Yi - Yj| which is maximum }

但对于非常大的输入它不会有效:(
谁有任何想法更好的算法？

解决方法

如果我们只考虑Xi< = Xj的结果,则只有两种情况需要考虑.
>如果Yi< = Yj,那么距离是(Xj Yj) - (Xi Yi)
>否则,距离为(Xj – Yj) – (Xi – Yi)

通过将其分解为这些情况,我已经摆脱了绝对值函数,使得更容易推断距离.

因此,我们只需选择具有最小和最大x y的点,并计算距离.然后选择具有最小和最大x-y的点,并计算距离.这两个距离中的一个是你的最大距离.

这可以在O(n)中完成,这是渐近最优的.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!