原題462. Minimum Moves to Equal Array Elements II

題目大意：

給你一串?dāng)?shù)字，對于每個數(shù)字，一次性可以移動一步(數(shù)值增加1或者減小1)，請問如何在最小的步伐數(shù)內(nèi)使所有的數(shù)字都相等

Example

Input:
[1,2,3]
Output:
2
Explanation:
Only two moves are needed (remember each move increments or decrements one element):
[1,2,3] => [2,2,3] => [2,2,2]

解題思路：

1. 錯誤思路：我的第一想法是求出這一串?dāng)?shù)字的平均數(shù)，再用每一個數(shù)減去這個平均數(shù)，求和，即輸出最短步伐，提交，WA,錯誤例子為[1,0,0,8,6],這里應(yīng)設(shè)為1，而不是平均數(shù)
2. 正確思路：我們先把這一列數(shù)按從小到大的順序排序，把基準(zhǔn)數(shù)k從最小數(shù)字開始，顯然此時不是最優(yōu)解，如果我們增加k，比k大的數(shù)字的步伐都會減1，比k小的數(shù)字的步伐都會加1，當(dāng)k左右的數(shù)字一樣多的時候，步伐最小。
   k-a[1]+k-a[2]+k-a[3]+...+a[N-3]-k+a[N-2]-k+a[N-1]-k,當(dāng)+k和-k的數(shù)目一樣多的時候，k就會被抵消，這樣就是后面的數(shù)減前面的數(shù)，這里要注意是奇數(shù)個還是偶數(shù)個

代碼1：

class Solution {
public:
    int minMoves2(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int ans=0,mid=0;
        if(nums.size()%2)
            mid=(nums.size()+1)/2;
        else
            mid=nums.size()/2;
        mid-=1;
        for(int i=0;i<mid;i++)
            ans-=(nums[i]);
        for(int i=mid+1;i<nums.size();i++)
            ans+=(nums[i]);
        if(nums.size()%2==0)
            ans-=nums[mid];
        return ans;
    }
};

改良代碼：對于奇數(shù)個，中間那個數(shù)不用參與運(yùn)算，即自己減自己為0；對于偶數(shù)個，中間那個數(shù)視為左邊的數(shù)，要參與運(yùn)算；所以可以使用(nums.size()+1)/2,即若size為奇數(shù)，上面式子增加1，若為偶數(shù)，值不變,（相對于size/2)

class Solution{
    public:
    int minMoves2(vector<int>& nums)
    {
        sort(nums.begin(),nums.end());
        int mid=nums.size()/2,ans=0;
        for(int i=0;i<mid;i++)
            ans-=nums[i];
        for(int i=(nums.size()+1)/2;i<nums.size();i++)//使用(size()+1)/2,如果size是奇數(shù)，那么值會+1，即從下一項(xiàng)開始；如果是偶數(shù)，值不變，仍然當(dāng)前項(xiàng)
            ans+=nums[i];
        return ans;
    }
};