找矩阵里的空间上的中点，非BFS搜索问题

Best Meeting Point 分析：如果只有一个点，best meeting point就在点上；如果有两个点，best meeting point 是这两点之间任意点；如果是三个点，best meeting point是在中间的那个点上；如果是N个点，如果N是偶数，best meeting point 是在最内层的两个点之间的任意点；如果是N是奇数，best meeting point是最中间那个点。所以可以得出结论，找到中点就可以使得总距离最短。

public class Solution {
    public int minTotalDistance(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {
            return 0;
        }

        List<Integer> rows = new ArrayList<Integer>();
        List<Integer> cols = new ArrayList<Integer>();
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    rows.add(i);
                    cols.add(j);
                }
            }
        }

        Collections.sort(cols); // sort的这一步可以用quickselect来优化。
        int row_mid = rows.get(rows.size() / 2);
        int col_mid = cols.get(cols.size() / 2);

        int sum = 0;
        for (int i = 0; i < rows.size(); i++) {
            sum += Math.abs(row_mid - rows.get(i));
        }
        for (int i = 0; i < cols.size(); i++) {
            sum += Math.abs(col_mid - cols.get(i));
        }

        return sum;
    }
}

Minimum Moves to Equal Array Elements II, 跟上一题一样，就是找中位数的问题。同样，sort的那一步可以用quickselect来优化。

public class Solution {
    public int minMoves2(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return 0;
        }

        Arrays.sort(nums);
        int mid = nums[nums.length / 2];

        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += Math.abs(mid - nums[i]);
        }
        return sum;
    }
}