462. 最少移动次数使数组元素相等 II

要求：如题
思路：三个元素abc，到中位数距离：c-a，到平均数距离：c-a+|b-(a+b+c)/3|
到众数举个反例：11234，距离6，中位数距离4
暂无严格证明
偶数时任一均可
法一：直接相加，击败57%

class Solution {
public:
    int minMoves2(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int sum=0;
        for(int num:nums)
            sum+=abs(nums[nums.size()/2]-num);
        return sum;
    }
};

优化一下也是57%

class Solution {
public:
    int minMoves2(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int sum=0,l=0,r=nums.size()-1;
        while(l<r){
            sum+=nums[r]-nums[l];
            ++l;--r;
        }
        return sum;
    }
};

法二：对sort加速，用快排partition方法，即找一个数进行partition后其位置在中间，类似二分了，注意不加随机的话击败12%，加了89%

class Solution {
public:
    int partition(int l,int r,vector<int>& nums){
        int ran=rand()%(r-l+1)+l;
        swap(nums[ran],nums[l]);
        int pivot=nums[l];
        int i=l,j=r;
        while(i<j){
            while(i<j&&nums[j]>=pivot)--j;
            while(i<j&&nums[i]<=pivot)++i;
            swap(nums[i],nums[j]);
        }
        swap(nums[l],nums[i]);
        return i;
    }
    int minMoves2(vector<int>& nums) {
        int mid=nums.size()/2;
        int l=0,r=nums.size()-1;
        while(true){
            int index=partition(l,r,nums);
            if(index==mid)break;
            else if(index>mid)r=index-1;
            else l=index+1;
        }
        int sum=0;
        for(int& num:nums)
            sum+=abs(num-nums[mid]);
        return sum;
    }
};