296. 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.
本题可以归结为数学问题，让我们求最佳的开会地点，A————P————B，从一维上面来考虑，假如P为最佳的点，那么P一定是在AB的中间，如果在左面或者右面，则距离就大于AB的距离了。四个点的情况如下：C———A——P——B——D，P也一定位于AB之间，而三个点的情况C——A——B，P一定位于刚好A点的距离，此时距离最小。扩展二维距离也是类似的，实现的时候需要注意，一定要把点分别按照row从小到大和col从小到大排序。
代码如下：
1 public class Solution { 2 public int minTotalDistance(int[][] grid) { 3 int m = grid.length; 4 int n = grid[0].length; 5 List<Integer> row = new ArrayList<>(); 6 List<Integer> col = new ArrayList<>(); 7 for(int i=0;i<m;i++){ 8 for(int j=0;j<n;j++){ 9 if(grid[i][j]==1){ 10 row.add(i); 11 col.add(j); 12 } 13 } 14 } 15 return getMin(row)+getMin(col); 16 } 17 public int getMin(List<Integer> list){ 18 int i=0; 19 int j=list.size()-1; 20 Collections.sort(list); 21 int res = 0; 22 while(i<j){ 23 res+=list.get(j--)-list.get(i++); 24 } 25 return res; 26 } 27 } 28 // the run time of the O(mnlogn).the space complexity could be O(m+n);