Given a non-empty integer array, find the minimum number of moves required to make all array elements equal, where a move is incrementing a selected element by 1 or decrementing a selected element by 1.

You may assume the array’s length is at most 10,000.

Example: 

1
2
3
4
5
6
7
8
9
10
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]

思路

Note that the explanation below is a leetcode discussion solution, my solution is actually figured out by finding out specific pattern in the question.

Imagine the nums are sorted, and the final value is k, we start find k from the first element.

If we increase k, the elements <= k will need move one step more, and the elements > k will need to move one step less.

If there are more elements > k than elements <= k, we should increase k to minimize the moves.

So we just increase k, until k reach the median of of the nums array. By then, the number of elements <= k equals to that of elements > k. (There is a slight different when the number of array is odd, but it’s similar).

If we keep increasing k after k reach the median of the array, more numbers >k than <= k, and more moves needed, so we should stop.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def minMoves2(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()
        length = len(nums)
        res  = 0
        mid = length / 2
        for i in nums:
            res += abs(nums[mid] - i)
        return res