Minimum Moves to Equal Array Elements

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作为数组的数需要靠近的目标，假设原数列中有m个小于等于K的数，有n个大于k的数。 （1）如果m

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 总结 最开始思考这问题的时候用动态规划来解，程序也能做出来，但是复杂度比这个算法高，代码量大，之后看别人求解时发现这种方法更优雅，更高效。