坐标分开考虑 中点问题

296. Best Meeting Point

首先是把行和列分开考虑 因为distance(p1, p2) =|p2.x - p1.x| + |p2.y - p1.y| 本质上是行和列的叠加

再者考虑每一行每一列 最短距离是当位置设置在线段中点的时候 在求的时候设置两个指针头尾扫计算距离

关键是中点距离最小是怎么得到的？？

public class Solution {
    /*
      Key point is the Algorithm, to divide the problem into rows and colomns 
      对于每一行的任意两个点，最短距离就是他们的横坐标之差
    */
    public int minTotalDistance(int[][] grid) {
        List<Integer> row = new ArrayList();
        List<Integer> col = new ArrayList();
        int l = grid.length;
        int c = grid[0].length;
        for(int i = 0;i < l;i++){
            for(int j = 0;j < c;j++){
                    row.add(i);
                    col.add(j);
                }
            }
        }
        //sort and add the list 
        Collections.sort(row); 
        Collections.sort(col);
        return minDistance(row) + minDistance(col);
    }
    public int minDistance(List<Integer> list){
        int result = 0;
        int start = 0;
        int end = list.size() - 1;
        while(start < end){
            result += list.get(end--) - list.get(start++);
        }
        return result;
    }
}

The same technique also applies here:

462. Minimum Moves to Equal Array Elements II

Reverse Thinking

453. Minimum Moves to Equal Array Elements

//adding 1 to (n - 1)numbers are like subtract 1 from one number think reversely here

//subtract 1 by 1 until we reach the minimum of all numbers

//adding 1 to (n - 1)numbers are like subtract 1 from one number think reversely here 
//subtract 1 by 1 until we reach the minimum of all numbers 
  public class Solution {
    public int minMoves(int[] nums) {
        if (nums.length == 0) return 0;
        int min = nums[0];
        for (int n : nums) min = Math.min(min, n);
        int res = 0;
        for (int n : nums) res += n - min;
        return res;
    }
  }