LC296. Best Meeting Point
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 - 0
The point (0,2) is an ideal meeting point, as the total travel distance of 2+2+2=6 is minimal. So return 6.
题目要求找到到达所有1曼哈顿距离之和最小的点。从1D入手，如果要找一点到两个定点距离之和最小，那一定在这个线段中间任取一点，3个点就取中间那一点。1D和2D道理相同。所以统计每行每列有多少人，然后使上下左右的人数分别相等即是最短曼哈顿距离。
public class Solution {
public int minTotalDistance(int[][] grid) {
// 1D -> let numbers in right side and left side be the same
// 2D -> left == right && above == below
if(grid == null) return 0;
int row = grid.length, col = grid[0].length;
int[] row_sum = new int[col];
int[] col_sum = new int[row];
for(int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
row_sum[j] += grid[i][j];
col_sum[i] += grid[i][j];
}
} // for
return findMin(col_sum) + findMin(row_sum);
}
private int findMin(int[] array){
// let left == right
// must begin from -1/length not 0/length-1, and use --j,++i not j-- i++
int i = -1, j = array.length;
int res = 0, left = 0, right = 0;
while(i != j){
if(left > right){
res += right;
right += array[--j];
}else{
res += left;
left += array[++i];
}
} // while
return res;
}
}
O(mn)复杂度。
说起来看到曼哈顿距离，想起了我的毕设。。。