Leetcode 462 Minumum Moves to Equal Array Elements II

发表于 |

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:
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]

分析：
也就是将所有数变成同一个数的花费，数组长度不超过10000，说明n^2的方法不行

思路：
我们先作几个简答的分析，比如一个有序数组，根据长度不同我们来依次分析
1.长度为3，[a,b,c]，那么显然都往b靠花费最小（这个很容易证）
cost = c-b + b-a = c-a
2.长度为4，[a,b,c,d],先分析往b靠好还是往c靠好
cost_b = d-b + c-b + b-a = d+c - (a+b)
cost_c = d-c + c-b + c-a = d+c - (a+b)
3.长度为5，[a,b,c,d,e]，显然是往c靠
cost = e-c + d-c + c-b + c-a = d+e - (a+b)
依次类推，我们发现花费就应该是数组的后半段减去数组的前半段，分奇偶判断一下即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def minMoves2(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()
        index = len(nums)//2
        if len(nums) % 2 == 1:
            return sum(nums[index+1:]) - sum(nums[:index])
        else:
            return sum(nums[index:]) - sum(nums[:index])


29 / 29 test cases passed.
difficulty: medium
Runtime: 61 ms