作者 | 刘助教 & ben 助教
编辑 | Freya Han
专栏 | 九章算法
给定一个长度为n的非空整数数组，找出使数组所有元素均相等的最少操作数，其中一次操作将其中n-1个数加上1。
输入
: [1,2,3]
输出
: 3
说明
:
最少3次操作到达要求：
[1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]
将n-1个数加1，相当于将所有数都加1，再将其中一个数减去1。
将所有数都加1这个操作，其实不会改变任何数的相对大小，也就是所有数两两之间的差都是不会变的，这对于要使所有元素均相等的目标来说没有影响，所以可以忽略这一部分。
那么问题就变成每次选个数减1来达到目标的最小次数。
要使次数最小，而且每次只能将元素减1，故应当把所有数减到与最小值相等。
若n个元素为a(0),a(1),……,a(n-1)，其中最小值为min，则答案为a(0)+a(1)+……+a(n-1)-min*n。
只需求出n个数中的最小值以及它们的和来计算即可，时间复杂度为O(n)。
Follow up
：如果一步操作可以加1或减1，那么如何解答
此题比较简单，能理清思路给出解答即可hire。
http://www.lintcode.com/zh-cn/problem/median/
http://www.jiuzhang.com/solution/minimum-moves-to-equal-array-elements/
给定一个非空整数数组，计算最少的操作的数量使得整个数组的元素全部相等。
一个操作的定义为选择一个元素+1或者-1。
你可以假定这个数组的长度最大不超过10000
输入:
[1,2,3]
输出:
2
只需要2步即可 [1,2,3] => [2,2,3] => [2,2,2]
a.
在之前的题解最少操作数使数组元素相等I中，我们已经了解了最少操作数使数组元素相等I的解法。
对于II，我们尝试继续用I的思路，但这一次我们增加了“-”操作。
一个自然的想法是，我们尝试把所有数字都往“中间”靠拢，也就是把中位数作为其他数转换的目标，接下来我们来证明这个结论。
b.
假设数组中有n个元素，各个元素为A[1....N]，
我们把目标值(所有值转换的目标，下同)初始值设为X=-max(使这N个元素数轴上均在X右边)，
操作数sum=∑(A[i]-X) 这时我们把X右移一位，可得sum=∑(A[i]-(X+1))=∑(A[i]-X)-N ，
我们发现，X每往右边移动一位(X始终小于min(A[i]))，答案都会减少N。
我们把X移到min(A[i])处继续往右移，当X位于[min(A[i]),max(A[i])]时，每向右移一位，对于X左边的数来说，它们需要操作的次数都会+1，对于X右边的数来说，它们需要的操作次数都会-1。
设X左边有L个数，右边有R个数。
每次右移后sum=sum+L-R，很明显，随着X的右移，R越来越小，L越来越大，
当R大于L时，sum逐渐减小，
当R小于L时，sum逐渐增大，
我们此时就要找到L==R的时刻，即sum取最小的时刻，
很明显，目标值X就是这个数组的中位数(当N为偶数时，目标值X为[A[N/2],A[N/2+1]中的任意值)。
c.
此时我们的目标就是如何找到这个中位数，最简单的方法是排序这个数组，中位数即A[N/2]，时间复杂度为O(nlogn)。
或者用大小为N/2的优先队列做，时间复杂度为O(nlog(n/2))
。
我们可以用快速排序的思想----快速选择算法来取得这个中位数，时间复杂度为O(n)
本题难度适中，解法多样，难点在于能否想到最优解是中位数，一般来说作为Minimum Moves to Equal Array Elements I的follow up出现。
如果能用quick select取代sort，那么面试官会对给你strong hire的评价。
http://www.lintcode.com/zh-cn/problem/median/
