Log*_*est 8 algorithm optimization
这里的问题是找到所有整数点的集合,它给出了来自给定点集的所有曼哈顿距离的最小总和!
例如:
让我们有一组给定的点{P1,P2,P3 ... Pn}
基本问题是找到一个点X,它将在点{P1,P2,P3 ... Pn}的所有距离上具有最小总和.
即| P1-X | + | P2-X | + .... + | Pn-X | = D,其中D将在所有X上最小.
更进一步,可以有多于一个满足上述条件的X值.也就是说,可能有多个X可以给出相同的值D.所以,我们需要找到所有这样的X.
任何人都可以想到的一个基本方法是找到输入的中位数,然后对这篇文章中提到的坐标进行暴力破解.
但是这种方法的问题是:如果中位数给出两个非常分开的值,那么我们最终会强制所有在给定时间内永远不会运行的点.
那么,是否存在任何其他方法即使在点相距很远时也会给出结果(中位数给出的范围大约为10 ^ 9).
您可以分别考虑X和Y,因为它们相互独立地增加了距离.这减少了在线上n个点找到与其他点之间的最小距离和的点的问题.这很简单:两个中位数(包括两个)之间的任何点都将满足这一点.
证明:如果我们有一个偶数点,那么将有两个中位数.两个中位数之间的点将在左侧具有n/2个点,在右侧具有n/2个点,并且具有到S的那些点的总距离.
如果我们将它向左移动一个点,S将上升n/2 (因为我们离开最右边的点)并向下移动n/2 (因为我们向最左边的点移动) ),总体S保持不变.在我们达到最左边的中间点之前,这是正确的.当我们向左移动最左边的中间点时,我们现在有(n/2 + 1)点到右边,而(n/2 - 1)指向左边,所以S上升了两个.继续向左只会进一步增加S.
按照相同的逻辑,最右边中间右边的所有点也有更高的S.
如果我们有奇数个点,则只有一个中位数.使用与上面相同的逻辑,我们可以证明它具有最低的S值.
如果中位数给你一个 10^9 量级的区间，那么该区间中的每个点都与其他点一样好。
因此，根据您稍后想要对这些点执行的操作，您可以返回范围或枚举该范围内的点。没办法绕过去..
显然，在二维中你会得到一个边界矩形，在三维中你会得到一个边界长方体等等。
结果始终是为每个维度获得的范围的笛卡尔积，因此您可以返回这些范围的列表作为结果。