题目地址：https://leetcode.com/problems/minimum-moves-to-equal-array-elements-ii/description/
题目描述
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.
Youmay 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]
题目大意
题目短的一般都不难。题意是求把一个数组所有的数都弄相等最少需要多少步。一步可以是把某个数字增加1或者把某个数字减少1.
解题方法
方法一：排序
题意已经明确了，把数字调整相等的最小步数，一定是把大数变小，把小数变大，最后都达到其中位数（注意不是均值）。最小化全部/平均距离是中位数的一个显著的性质。
Minimizing the total/average distance is just a prominent property of a median.
可以举例来看：
对于 [1, 5, 6]，其均值是4， 中位数是5.
如果把所有的数字都移动到4，需要sum([3,1,2])=6步；
如果把所有的数字都移动到5，需要sum([4,0,1])=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])
1 2 3 4 5 6 7 8
同样使用排序去做。新学会了~i运算。即求反。python支持负数索引，所以这个运算符很实用啊。
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)])
1 2 3 4 5 6 7 8
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;
}
};
1 2 3 4 5 6 7 8 9 10 11 12 13
方法二：直接找中位数
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;
}
};
1 2 3 4 5 6 7 8 9 10 11 12 13
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发