1问题描述 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. 2简要分析 思路是数学中函数极值点的判断。设我们需要的目标点为k，原数列中小于等于k的数的个数为m,大于k的点的个数为n个。 （1）当m小于n时，我们应该增加k。因为k增加1会使得n个大于k的数使用的步数减少n，每个数减少1，同样会使得小于等于k的m个数使用的步数增加m，每个数增加1，因此，减少的步数多于增加的步数。当m刚好第一次大于等于n时那个k值是我们需要的目标点。 （2）当m大于等于n时，如果我们继续增加k的值，则减少的步数不足以抵消增加的步数，所以总体的步数会增加。 从上面分析可以知道，我们需要求使得第一次m大于等于n成立的k值。而这等价于求数列中的中位数。 使用递归的策略，随机选择一个值m，将原序列分为两个部分，一部分比m小，一部分比m大。可以求得原序列任意第k个大小的数。期望复杂度为O（n）。 3代码实现
int minMoves3(vector<int>& nums) { int n = nums.size(); auto it = nums.begin() + n / 2; nth_element(nums.begin(), it, nums.end()); int median = *it; int total = 0; for (auto &i : nums) total += abs(i - median); return total; }4总结 一开始解决这个问题使用了动态规划，解决的不够优雅。
