C++ solution


  • 0
    I
    class Solution {
    public:
        long minMoves(vector<int>& nums, int target)
        {
            long res = 0;
            for(int i = 0; i < nums.size(); ++i)
               res += abs(nums[i] - target);
            return res;
        }
    
        int minMoves2(vector<int>& nums) {
            sort(nums.begin(),nums.end());
            return minMoves(nums,nums[nums.size()/2]);
        }
    };
    

  • 0
    Z

    I don't know why all number should close to the middle one? how to prove? I use the binary Search to get the answer.


  • 0
    I

    think about this,

    [110, n, 120], 110 <= n <= 120, the answer is always 10.

    than add 2 more numbers:

    [100, 110, n, 120, 130], for the [100, n, 130] part, the answer is always 30 if 100 <= n <= 130. and we can always chose n between 110 ~ 120 to satisfy [110, n, 120].

    now add two more number, and two more, and two more.....

    you can see that 'n' is actually the median of the sorted array!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.