# 462. Minimum Moves to Equal Array Elements II 最少移动次数使数组元素相等 II

@TOC

## # 题目描述

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

## # 解题方法

### # 方法一：排序

Minimizing the total/average distance is just a prominent property of a median.

``````对于 [1, 5, 6]，其均值是4， 中位数是5.

``````

``````class Solution(object):
def minMoves2(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
median = sorted(nums)[len(nums) / 2]
return sum([abs(num - median) for num in nums])
``````

The ~ operator is the same as in C++, so 0, 1, 2, ... get turned into -1, -2, -3, .... But C++ doesn’t support negative indexing. In Python, index -1 means the last element, index -2 means the next-to-last element, etc.

``````class Solution(object):
def minMoves2(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
nums.sort()
return sum([nums[~i] - nums[i] for i in range(len(nums) / 2)])
``````

C++排序解法同样很简单。

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

### # 方法二：直接找中位数

C++有直接找中位数的函数nth_element()，参数设置成N/2就能把中位数的位置给固定了。这种做法可以不用排序了，速度也更快。

``````class Solution {
public:
int minMoves2(vector<int>& nums) {
const int N = nums.size();
int mi = N / 2;
nth_element(nums.begin(), nums.begin() + mi, nums.end());
int res = 0;
for (int n : nums) {
res += abs(n - nums[mi]);
}
return res;
}
};
``````

## # 日期

2018 年 3 月 4 日 2018 年 12 月 14 日 —— 12月过半，2019就要开始