c********l
发帖数: 8138 | 1 已知平面上有N个点，找到其中某个点P，使得P到其余所有点的Manhattan距离之和最短
网上Google了一下解决方案，找到的都不满意
1. stackoverflow上给出了一种最简便的解法，但该解法只是找到平面坐标上的一
个(X,Y)的整数坐标，但是该坐标不一定是N个点中的某个点。
2. 另一些解法，虽然用图论的角度给出了最小生成树，但是看得云里雾里.... |
p***o
发帖数: 1252 | 2 What complexity are you looking for? O(n log n) time seems possible.
1 sort according to x coordinates
2 scan from left to right, for each point, compute the total
Manhattan distance on x from it to the rest of points
(O(n) time for the left most point and O(1) for each of the rest)
3 do 1 and 2 for y coordinates
4 add up the distances on x and y for each point and locate the minimum
【在 c********l 的大作中提到】
: 已知平面上有N个点，找到其中某个点P，使得P到其余所有点的Manhattan距离之和最短
: 网上Google了一下解决方案，找到的都不满意
: 1. stackoverflow上给出了一种最简便的解法，但该解法只是找到平面坐标上的一
: 个(X,Y)的整数坐标，但是该坐标不一定是N个点中的某个点。
: 2. 另一些解法，虽然用图论的角度给出了最小生成树，但是看得云里雾里....
|
d******e
发帖数: 2265 | 3 尼玛，当年老子被狗用这道题虐了。
面前没睡好。第二天晕着做，晕着听讲。
最佳解法，不太记得了，貌似是O(n)的。
免冠的算法现在不记得了。
就我自己刚才想了一下，算法如下。
找出所有点的mbb.
则左边上必然至少有一点，右边也是。考虑到是马哈顿距离，最有点的x距离和y距离独
立，(自己和左图试试）
全部坍塌到x周上。
则，和为 ：
x＝ n_1 times x_1 + n_2 x_2 ....
起重心为 x／n,则为x 最优x。
同理求最优y.
则为P = (x,y)
【在 c********l 的大作中提到】
: 已知平面上有N个点，找到其中某个点P，使得P到其余所有点的Manhattan距离之和最短
: 网上Google了一下解决方案，找到的都不满意
: 1. stackoverflow上给出了一种最简便的解法，但该解法只是找到平面坐标上的一
: 个(X,Y)的整数坐标，但是该坐标不一定是N个点中的某个点。
: 2. 另一些解法，虽然用图论的角度给出了最小生成树，但是看得云里雾里....
|
i**i
发帖数: 1500 | 4 最小生成树复杂度较高．并且实现挺麻烦的．
还是找出理论上的中心，然后每个点和这个中心比较简单．
【在 c********l 的大作中提到】
: 已知平面上有N个点，找到其中某个点P，使得P到其余所有点的Manhattan距离之和最短
: 网上Google了一下解决方案，找到的都不满意
: 1. stackoverflow上给出了一种最简便的解法，但该解法只是找到平面坐标上的一
: 个(X,Y)的整数坐标，但是该坐标不一定是N个点中的某个点。
: 2. 另一些解法，虽然用图论的角度给出了最小生成树，但是看得云里雾里....
|
w***g
发帖数: 5958 | 5 你这个问题用专有名词讲叫 find the medoid under Manhattan/L1 distance。如果对
Manhattan distance做K-Medoid聚类的话是一个超频繁调用的操作。不知道你的最小生
成树的解法是从哪儿看来的。前面database指出了解这个问题的关键，就是在
Manhattan distance下X和Y独立。不过他的解法我实在没有看明白，只能猜一下。
我们的目标是任意给P点中的一点可以用O(1)算出所有点(P到自己的距离是0，包不包含
无所谓）到该点的距离之和sum(P)。这样所有点过一遍用O(n)就可以找出最优点。
这个sum(P)又可以分解 sum_x(P_x)+sum_y(P_y)。 sum_x和sum_y的算法相同。下面用
计算sum_x加以说明。
加入有一串值x1, x2, ...，要计算任意一个xi的sum_x(xi)值。可以对所有x排序O(
nlogn)。
x1, x2, x3, ...
然后对各个i计算 left_i = x1 + x2 + ... + xi-1
right_i = x{i+1} + x{i+2} ... + xn
这个计算耗时O(n)，而且这个算过一遍以后对所有的x都有效。
然后 sum_x(x_i) = x_i * (i-1) - left_i + right_i - (n - i) * x_i
O(1)时间就可以算出。
最大的开销是排序，所以算法复杂度为O(nlogn)。
【在 c********l 的大作中提到】
: 已知平面上有N个点，找到其中某个点P，使得P到其余所有点的Manhattan距离之和最短
: 网上Google了一下解决方案，找到的都不满意
: 1. stackoverflow上给出了一种最简便的解法，但该解法只是找到平面坐标上的一
: 个(X,Y)的整数坐标，但是该坐标不一定是N个点中的某个点。
: 2. 另一些解法，虽然用图论的角度给出了最小生成树，但是看得云里雾里....
|
c********l
发帖数: 8138 | 6 这么做最后被证明是错的....
【在 i**i 的大作中提到】
: 最小生成树复杂度较高．并且实现挺麻烦的．
: 还是找出理论上的中心，然后每个点和这个中心比较简单．
|
i**i
发帖数: 1500 | 7 怎么证明的？
看一下一维的情况，二位可以简单地从一维扩展过来。
首先一维的理论中心就是平均值。然后看哪个点离中心最近，这个点就是所求。 距离
的值可以根据（左右点的个数之差）*离平均值的距离+原距离得到。
有问题吗？
【在 c********l 的大作中提到】
: 这么做最后被证明是错的....
|
c********l
发帖数: 8138 | 8 我就是先找的一个“理论的距离最小点”，记为P
然后找所有点中距离P最小的点Q
最后计算所有点到Q的mht距离之和
结果被google code jam报错，但没有说具体哪里错。
当然，也可能是我的implementation错了，换句话可能算法是对的，但实现上有bug
【在 i**i 的大作中提到】
: 怎么证明的？
: 看一下一维的情况，二位可以简单地从一维扩展过来。
: 首先一维的理论中心就是平均值。然后看哪个点离中心最近，这个点就是所求。 距离
: 的值可以根据（左右点的个数之差）*离平均值的距离+原距离得到。
: 有问题吗？
|
c********l
发帖数: 8138 | 9 感谢你和pptwo 的解答！
换句话，O(nlogn)就是最优解，不可能有O(n)了？
如果阿三面试官说要继续改进，那肯定是被黑了？
【在 w***g 的大作中提到】
: 你这个问题用专有名词讲叫 find the medoid under Manhattan/L1 distance。如果对
: Manhattan distance做K-Medoid聚类的话是一个超频繁调用的操作。不知道你的最小生
: 成树的解法是从哪儿看来的。前面database指出了解这个问题的关键，就是在
: Manhattan distance下X和Y独立。不过他的解法我实在没有看明白，只能猜一下。
: 我们的目标是任意给P点中的一点可以用O(1)算出所有点(P到自己的距离是0，包不包含
: 无所谓）到该点的距离之和sum(P)。这样所有点过一遍用O(n)就可以找出最优点。
: 这个sum(P)又可以分解 sum_x(P_x)+sum_y(P_y)。 sum_x和sum_y的算法相同。下面用
: 计算sum_x加以说明。
: 加入有一串值x1, x2, ...，要计算任意一个xi的sum_x(xi)值。可以对所有x排序O(
: nlogn)。
|
i**i
发帖数: 1500 | 10 真的有问题。
【在 c********l 的大作中提到】
: 我就是先找的一个“理论的距离最小点”，记为P
: 然后找所有点中距离P最小的点Q
: 最后计算所有点到Q的mht距离之和
: 结果被google code jam报错，但没有说具体哪里错。
: 当然，也可能是我的implementation错了，换句话可能算法是对的，但实现上有bug
|
|
|
k**********g
发帖数: 989 | 11
弱问，不就是 P = ( median(X), median(Y) )吗？
【在 c********l 的大作中提到】
: 已知平面上有N个点，找到其中某个点P，使得P到其余所有点的Manhattan距离之和最短
: 网上Google了一下解决方案，找到的都不满意
: 1. stackoverflow上给出了一种最简便的解法，但该解法只是找到平面坐标上的一
: 个(X,Y)的整数坐标，但是该坐标不一定是N个点中的某个点。
: 2. 另一些解法，虽然用图论的角度给出了最小生成树，但是看得云里雾里....
|
c********l
发帖数: 8138 | 12 我顶楼已经写了
1. stackoverflow上给出了一种最简便的解法，但该解法只是找到平面坐标上的一
个(X,Y)的整数坐标，但是该坐标不一定是N个点中的某个点。
【在 k**********g 的大作中提到】
:
: 弱问，不就是 P = ( median(X), median(Y) )吗？
|
k**********g
发帖数: 989 | 13
actually,
Sum of mht from arbitrary point T to every point in set
= Sum of vertical distance from T to every point *above* T
+ Sum of vertical distance from T to every point *below* T
+ Sum of horizontal distance from T to every point *left of* T
+ Sum of horizontal distance from T to every point *right of* T
So, maybe the number of items (points) in each criterion do not equal,
despite point T being the "median / medoid point"
【在 c********l 的大作中提到】
: 我就是先找的一个“理论的距离最小点”，记为P
: 然后找所有点中距离P最小的点Q
: 最后计算所有点到Q的mht距离之和
: 结果被google code jam报错，但没有说具体哪里错。
: 当然，也可能是我的implementation错了，换句话可能算法是对的，但实现上有bug
|
l***i
发帖数: 1309 | 14 pptwo's solution is correct, the idea is that you can compute L1 distance
from point[i] to all other points, for every point i, in time O(nlogn). |
o******1
发帖数: 1046 | 15 曼哈顿距离跟是不是整数无关，只跟相对位置有关。这类题一般还要假设没有相等的坐
标。
如果是一维的，最优算法是O(N)。因为不需要sort整个数列，只要找到第(N+1)/2个数
（if N is odd），或者找到floor(N+1)和ceiling(N+1)（if N is even）。
但是如果是2维或者更高维的，最优算法应该是O(NlgN)，因为不能事先确定最小距离点
的位置，所以必须把两个或者更多个维度的距离加起来，每个维度的距离的复杂度都是
(NlgN)。
要是面试官跟你说二维问题的复杂度也是O(N)的话，一定是忽悠你了。 |
