我试图计算一个大的2D输入的最大曼哈顿距离,输入由(x,y)s组成,我想要做的是计算这些坐标之间的最大距离小于O(n ^ 2)时间,我可以通过遍历所有元素来在O(n ^ 2)中完成它,例如：
*(两点(X1,Y1)和(X2,Y2)之间的曼哈顿距离为：| X1-X2 | | Y1-Y2 |)
*(两点(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)
>如果Yi< = Yj,那么距离是(Xj Yj) - (Xi Yi)
>否则,距离为(Xj – Yj) – (Xi – Yi)
通过将其分解为这些情况,我已经摆脱了绝对值函数,使得更容易推断距离.
因此,我们只需选择具有最小和最大x y的点,并计算距离.然后选择具有最小和最大x-y的点,并计算距离.这两个距离中的一个是你的最大距离.
这可以在O(n)中完成,这是渐近最优的.
