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表示人，0表示空地
原理：
- 由于
distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|，我们先计算出横坐标距离最短再计算出纵坐标距离最短。 - 对于直线上的若干点，最短的距离就是各个点之间的距离之和。（选最中间的点）
public class Solution {
public int minTotalDistance(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
List<Integer> I = new ArrayList<>(m);
List<Integer> J = new ArrayList<>(n);
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(grid[i][j] == 1){
I.add(i);
J.add(j);
}
}
}
return getMin(I) + getMin(J);
}
private int getMin(List<Integer> list){
int ret = 0;
Collections.sort(list);
int i=0, j = list.size()-1;
while(i<j){
ret += list.get(j--) - list.get(i++);
}
return ret;
}
}
二刷
同上。
