Minimum Moves to Equal Array Elements II && Best Meeting Point

这种矩阵找到最短距离，或者数组使所有数相等的题目，是用典型的排序双指针来做的。注意，这类题目的关键元素不是找average，而是找Median。

1. Minimum Moves to Equal Array Elements II
   https://leetcode.com/problems/minimum-moves-to-equal-array-elements-ii/

做法1： 排序，双指针:

int minMoves2(vector<int>& nums) {
        if(nums.empty()) return 0;
        sort(nums.begin(), nums.end());
        int left = 0, right = nums.size()-1;
        int moves = 0;
        while(left < right){
            moves += nums[right]-nums[left];
            left++;
            right--;
        }
        return moves;
    }

做法2： 这道题其实是找到median，然后求所有数与mediam的差值就可以。找median可以用quick select，这样把复杂度降低到了 O(n)

int minMoves2(vector<int>& nums) {
        if(nums.empty()) return 0;
        int mid = findNumber(nums, nums.size()/2);
        int sum = 0;
        for(int i=0; i<nums.size(); i++){
            sum += abs(nums[i] - mid);
        }
        return sum;
    }
    
    int findNumber(vector<int>& nums, int k){
        int left = 0, right = nums.size()-1;
        while(left <= right){
            int mid = partition(nums, left, right);
            if(mid == k) return nums[mid];
            else if(mid > k) right = mid-1;
            else left = mid+1;
        }
        return -1;
    }
    
    int partition(vector<int>& nums, int l, int r){
        int left = l, right = r;
        int pivot = nums[left];
        while(left < right){
            while(left < right && nums[right] >= pivot){
                right--;
            }
            if(left != right){
                nums[left++] = nums[right];
            }
            while(left < right && nums[left] <= pivot){
                left++;
            }
            if(left != right){
                nums[right--] = nums[left];
            }
        }
        nums[left] = pivot;
        return left;
    }

Best Meeting Point:
https://leetcode.com/problems/best-meeting-point/

这道题其实就是把一维变成两维。而两维是要分开做的。分开的方法是，我们分别把row，和col存在两个数组里，然后找他们的median，求差。

int minTotalDistance(vector<vector<int>>& grid) {
        if(grid.empty() || grid[0].empty()) return 0;
        int row = grid.size(), col = grid[0].size();
        
        vector<int> rows;
        vector<int> cols;
        for(int i=0; i<row; i++){
            for(int j=0; j<col; j++){
                if(grid[i][j] == 1){
                    rows.push_back(i);
                    cols.push_back(j);
                }
            }
        }
        sort(rows.begin(), rows.end());
        sort(cols.begin(), cols.end());
        int diff = 0;
        int left = 0, right = rows.size()-1;
        while(left < right){
            diff += abs(rows[right] - rows[left]) + abs(cols[right] - cols[left]);
            left++; right--;
        }
        return diff;
    }