[Leetcode] Best Meeting Point 最佳见面点 - SegmentFault
A group of two or more people wants to meet and minimize the total travel distance. You are given a 2D grid of values 0 or 1, where each 1 marks the home of someone in the group. The distance is calculated using Manhattan Distance, where distance
For example, given three people living at (0,0), (0,4), and (2,2):
http://algobox.org/best-meeting-point/
Since the distance is computed using the Manhattan Distance, we can decompose this 2-d problem into two 1-d problems and combine (add) their solutions. In fact, the best meeting point is just the point that comprised by the two best meeting points in each dimension.
For the 1d case, the best meeting point is just the median point.
The neat
Originally I used
public int minTotalDistance(int[][] grid) { int m = grid.length, n = grid[0].length; int total = 0, Z[] = new int[m*n]; for (int dim=0; dim<2; ++dim) { int i = 0, j = 0; if (dim == 0) { for (int x=0; x<n; ++x) for (int y=0; y<m; ++y) if (grid[y][x] == 1) Z[j++] = x; } else { for (int y=0; y<m; ++y) for (int g : grid[y]) if (g == 1) Z[j++] = y; } while (i < --j) total += Z[j] - Z[i++]; } return total; }
https://zyfu0408.gitbooks.io/interview-preparation/content/zhao_ju_zhen_li_de_kong_jian_shang_de_zhong_dian_f.html
如果只有一个点，best meeting point就在点上；如果有两个点，best meeting point 是这两点之间任意点；如果是三个点，best meeting point是在中间的那个点上；如果是N个点，如果N是偶数，best meeting point 是在最内层的两个点之间的任意点；如果是N是奇数，best meeting point是最中间那个点。所以可以得出结论，找到中点就可以使得总距离最短。
http://buttercola.blogspot.com/2015/10/leetcode-best-meeting-point.html
A group of two or more people wants to meet and minimize the total travel distance. You are given a 2D grid of values 0 or 1, where each 1 marks the home of someone in the group. The distance is calculated using Manhattan Distance, where distance
(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.For example, given three people living at (0,0), (0,4), and (2,2):
1 - 0 - 0 - 0 - 1 | | | | | 0 - 0 - 0 - 0 - 0 | | | | | 0 - 0 - 1 - 0 - 0The point(0,2)is an ideal meeting point, as the total travel distance of2+2+2=6is minimal. So return 6.http://www.chenguanghe.com/best-meeting-point/
首先,Manhattan Distance 的合为 sum(distance(p1, p2)) = sum(|p2.x - p1.x| + |p2.y - p1.y|)= sum(|p2.x - p1.x|)+sum(|p2.y - p1.y|). 也就是说, 可以分别计算x和y的合, 然后加起来.其次, 我们需要把2d的grid变成1d, 这里的窍门是, 我们可以证明, 所求的点, 就在其中某点的x或者y的坐标轴上. 所以, 而这点, 必然是1d下的median. http://math.stackexchange.com/questions/113270/the-median-minimizes-the-sum-of-absolute-deviationsSuppose we have a set S of real numbers that ∑s∈S|s−x|is minimal if x is equal to themedian.
所以, 我们需要count一下x轴上有多少个1的投影, 和y轴上有多少个1的投影. 就可以找到这个median. 这里我们不需要sorting, 因为投影本身就是已排序的.最后, 我们得到一个1d的array, 我们需要计算以上公式,即各点到median的值的合, 这里需要用two pointers, 因为array本身已经是排序过后的了, 所以我们只需要求两头的元素的差值的合, 就是他们到median的合.6是median,那么 (6-2)+(6-4) + (6-5) + (7-6) + (8-6) + (9-6) = 4 + 2+ 1+ 1+ 2+ 3 = 13 = (9-2) + (8-4) + (7-5)
public int minTotalDistance(int[][] grid) {ArrayList<Integer> r = new ArrayList<Integer>();ArrayList<Integer> l = new ArrayList<Integer>();for(int i = 0; i < grid.length; i++){for(int j = 0; j < grid[0].length; j++){if(grid[i][j] == 1)r.add(i);}}// rename l, r to xs, ys. rename min to getDistance/for(int j = 0; j < grid[0].length; j++){// project to x or y axisfor(int i = 0; i < grid.length; i++){if(grid[i][j] == 1)l.add(j);}}return min(r)+min(l);}public int min(ArrayList<Integer> ary) {int i = 0;int j = ary.size()-1;int sum = 0;while(i < j){sum += (ary.get(j) -ary.get(i));i++;j--;}return sum;}
public int minTotalDistance(int[][] grid) {
List<Integer> ipos = new ArrayList<Integer>();
List<Integer> jpos = new ArrayList<Integer>();
// 统计出有哪些横纵坐标
for(int i = 0; i < grid.length; i++){
for(int j = 0; j < grid[0].length; j++){
if(grid[i][j] == 1){
ipos.add(i);
jpos.add(j);
}
}
}
int sum = 0;
// 计算纵坐标到纵坐标中点的距离，这里不需要排序，因为之前统计时是按照i的顺序
for(Integer pos : ipos){
sum += Math.abs(pos - ipos.get(ipos.size() / 2));
}
// 计算横坐标到横坐标中点的距离，这里需要排序，因为统计不是按照j的顺序
Collections.sort(jpos);
for(Integer pos : jpos){
sum += Math.abs(pos - jpos.get(jpos.size() / 2));
}
return sum;
}
这道题让我们求最佳的开会地点，该地点需要到每个为1的点的曼哈顿距离之和最小，题目中给了我们提示，让我们先从一维的情况来分析，那么我们先看一维时有两个点A和B的情况,
______A_____P_______B_______
那么我们可以发现，只要开会为位置P在[A, B]区间内，不管在哪，距离之和都是A和B之间的距离，如果P不在[A, B]之间，那么距离之和就会大于A和B之间的距离，那么我们现在再加两个点C和D：
______C_____A_____P_______B______D______
我们通过分析可以得出，P点的最佳位置就是在[A, B]区间内，这样和四个点的距离之和为AB距离加上CD距离，在其他任意一点的距离都会大于这个距离，那么分析出来了上述规律，这题就变得很容易了，我们只要给位置排好序，然后用最后一个坐标减去第一个坐标，即CD距离，倒数第二个坐标减去第二个坐标，即AB距离，以此类推，直到最中间停止，那么一维的情况分析出来了，二维的情况就是两个一维相加即可，参见代码如下：
解法一：
class Solution { public: int minTotalDistance(vector<vector<int>>& grid) { vector<int> rows, cols; for (int i = 0; i < grid.size(); ++i) { for (int j = 0; j < grid[i].size(); ++j) { if (grid[i][j] == 1) { rows.push_back(i); cols.push_back(j); } } } return minTotalDistance(rows) + minTotalDistance(cols); } int minTotalDistance(vector<int> v) { int res = 0; sort(v.begin(), v.end()); int i = 0, j = v.size() - 1; while (i < j) res += v[j--] - v[i++]; return res; }
Before solving the 2D problem we first consider a 1D case. The solution is quite simple. Just find the median of all the x coordinates and calculate the distance to the median.
Alternatively, we can also use two pointers to solve the 1D problem. left and right are how many people one left/right side of coordinates
i/j. If we have more people on the left we let j decrease otherwise increase i. The time complexity is O(n) and space is O(1).
To be more clear, a better view is that we can think
i and j as two meeting points. All the people in [0, i] meet ati and all the people in [j, n - 1] meet at j. We let left = sum(vec[:i+1]), right = sum(vec[j:]), which are the number of people at each meet point, and d is the total distance for the left people meet at i and right people meet at j.
Our job is to let
i == j with minimum d.
If we increase
i by 1, the distance will increase by left since there are left people at i and they just move 1step. The same applies to j, when decrease j by 1, the distance will increase by right. To make sure the total distance d is minimized we certainly want to move the point with less people. And to make sure we do not skip any possible meet point options we need to move one by one.
For the 2D cases we first need to sum the columns and rows into two vectors and call the 1D algorithm. The answer is the sum of the two. The time is then
O(mn) and extra space is O(m+n)
Moreover, the solution is still
O(mn) with the follow up:What if there are people sharing same home? In other words the number in the grid can be more than 1.
public int minTotalDistance(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[] row_sum = new int[n], col_sum = new int[m];
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j) {
row_sum[j] += grid[i][j];
col_sum[i] += grid[i][j];
}
return minDistance1D(row_sum) + minDistance1D(col_sum);
}
public int minDistance1D(int[] vector) {
int i = -1, j = vector.length;
int d = 0, left = 0, right = 0;
while (i != j) {
if (left < right) {
d += left;
left += vector[++i];
} else {
d += right;
right += vector[--j];
}
}
return d;
}
http://www.cnblogs.com/jcliBlogger/p/4901473.htmlSince the distance is computed using the Manhattan Distance, we can decompose this 2-d problem into two 1-d problems and combine (add) their solutions. In fact, the best meeting point is just the point that comprised by the two best meeting points in each dimension.
For the 1d case, the best meeting point is just the median point.
3 int minTotalDistance(vector<vector<int>>& grid) { 4 int m = grid.size(), n = grid[0].size(); 5 vector<int> ii, jj; 6 for (int i = 0; i < m; i++) { 7 for (int j = 0; j < n; j++) { 8 if (grid[i][j]) { 9 ii.push_back(i); 10 jj.push_back(j); 11 } 12 } 13 } 14 sort(jj.begin(), jj.end()); 15 int c = ii.size(), s = 0, io = ii[c/2], jo = jj[c/2]; 16 for (int i : ii) s += abs(i - io); 17 for (int j : jj) s += abs(j - jo); 18 return s; 19 }https://leetcode.com/discuss/65366/o-mn-java-2ms
The neat
total += Z[hi--] - Z[lo++]-style summing is from larrywang2014's solution.Originally I used
total += abs(Z[i] - median)-style.public int minTotalDistance(int[][] grid) { int m = grid.length, n = grid[0].length; int total = 0, Z[] = new int[m*n]; for (int dim=0; dim<2; ++dim) { int i = 0, j = 0; if (dim == 0) { for (int x=0; x<n; ++x) for (int y=0; y<m; ++y) if (grid[y][x] == 1) Z[j++] = x; } else { for (int y=0; y<m; ++y) for (int g : grid[y]) if (g == 1) Z[j++] = y; } while (i < --j) total += Z[j] - Z[i++]; } return total; }
BucketSort-ish. Count how many people live in each row and each column. Only O(m+n) space.
public int minTotalDistance(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[] I = new int[m], J = new int[n];
for (int i=0; i<m; ++i)
for (int j=0; j<n; ++j)
if (grid[i][j] == 1) {
++I[i];
++J[j];
}
int total = 0;
for (int[] K : new int[][]{ I, J }) {
int i = 0, j = K.length - 1;
while (i < j) {
int k = Math.min(K[i], K[j]);
total += k * (j - i);
if ((K[i] -= k) == 0) ++i;
if ((K[j] -= k) == 0) --j;
}
}
return total;
}https://zyfu0408.gitbooks.io/interview-preparation/content/zhao_ju_zhen_li_de_kong_jian_shang_de_zhong_dian_f.html
如果只有一个点，best meeting point就在点上；如果有两个点，best meeting point 是这两点之间任意点；如果是三个点，best meeting point是在中间的那个点上；如果是N个点，如果N是偶数，best meeting point 是在最内层的两个点之间的任意点；如果是N是奇数，best meeting point是最中间那个点。所以可以得出结论，找到中点就可以使得总距离最短。
public int minTotalDistance(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {
return 0;
}
List<Integer> rows = new ArrayList<Integer>();
List<Integer> cols = new ArrayList<Integer>();
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 1) {
rows.add(i);
cols.add(j);
}
}
}
Collections.sort(cols); // sort的这一步可以用quickselect来优化。
int row_mid = rows.get(rows.size() / 2);
int col_mid = cols.get(cols.size() / 2);
int sum = 0;
for (int i = 0; i < rows.size(); i++) {
sum += Math.abs(row_mid - rows.get(i));
}
for (int i = 0; i < cols.size(); i++) {
sum += Math.abs(col_mid - cols.get(i));
}
return sum;
}http://buttercola.blogspot.com/2015/10/leetcode-best-meeting-point.html
