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|攀涵，我們先計(jì)算出橫坐標(biāo)距離最短再計(jì)算出縱坐標(biāo)距離最短祝拯。 - 對(duì)于直線上的若干點(diǎn)，最短的距離就是各個(gè)點(diǎn)之間的距離之和。（選最中間的點(diǎn)）
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;
}
}
二刷
同上。
