Minimum Sum of Manhattan Distance

Shamelessly copied from:http://www.fgdsb.com/2015/01/02/minimum-manhattan-distance/

已知平面上有N个点，找到其中某个点P，使得P到其余所有点的Manhattan距离之和最短并求出这个最短距离。

因为是曼哈顿距离，所以可以把x轴和y轴分离开来计算。

1. 针对x坐标对所有点排序。
2. 求一个数组，每个元素为对应点到其他所有点的在x轴上的距离和。
   这一步需要O(n)的算法，具体思路是，记录两个数组，left和right:
   left[i] = x[1] + x[2] + ... + x[i-1]
right[i] = x[i+1] + x[i+2] ... + x[n]
   然后对每个点
   sum[i] = x[i] * i - left[i] + right[i] - (n - 1 - i) * x[i]
3. 针对y坐标重复1和2的计算。
4. 求得每个点在x和y上的1D曼哈顿距离和之后，可以遍历所有点，直接找出最小值。

算法复杂度即为sort的复杂度,O(nlogn)

一个参考解答，同时也说了Follow up: 九章算法

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

map<pair<int,int>,int> mht_sum(const vector<Point>& pts, bool get_x) { int n = (int)pts.size(); vector<int> left(n), right(n); int sum = 0; for(int i = 0; i < n; ++i) { left[i] = sum; sum += get_x ? pts[i].x : pts[i].y; } sum = 0; for(int i = n - 1; i >= 0; --i) { right[i] = sum; sum += get_x ? pts[i].x : pts[i].y; } map<pair<int,int>,int> ret; for(int i = 0; i < n; ++i) { int p = get_x ? pts[i].x : pts[i].y; ret[{pts[i].x,pts[i].y}] = p * i - left[i] + right[i] - (n-1-i) * p; } return ret; } int min_mht_dis(vector<Point> pts) { sort(pts.begin(), pts.end(), [&](const Point& p0, const Point& p1){ return p0.x < p1.x; }); auto x_sums = mht_sum(pts, true); sort(pts.begin(), pts.end(), [&](const Point& p0, const Point& p1){ return p0.y < p1.y; }); auto y_sums = mht_sum(pts, false); int ret = INT_MAX; for(int i = 0; i < pts.size(); ++i) { ret = min(ret, x_sums[{pts[i].x,pts[i].y}] + y_sums[{pts[i].x,pts[i].y}]); } return ret; }

Check the original question at MITBBS