题目描述

给定一个非空整数数组，找到使所有数组元素相等所需的最小移动数，其中每次移动可将选定的一个元素加 1 或减 1。 您可以假设数组的长度最多为 10000。

样例

输入：
[1,2,3]

输出：
2

解释：
只有两个动作是必要的（记得每一步仅可使其中一个元素加 1 或减 1）： 

[1,2,3]  =>  [2,2,3]  =>  [2,2,2]

算法

(贪心) $O(n)$

1. 凭直觉可以想到，最终改变为的元素值一定是数组的中位数。若中位数不存在，则两个位于中间值（含）的任意一个数字都是最优值。
2. 通过反证法，可以很容易地证明若中位数不是最终的值，可以通过将最终的值改为中位数减少操作次数。
3. 使用 nth_element 可以在 $O(n)$ 的时间复杂度内取得中位数。

时间复杂度

• 取得中位数的时间复杂度为 $O(n)$，统计答案的时间复杂度为 $O(n)$，故总时间复杂度为 $O(n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int minMoves2(vector<int>& nums) {
        nth_element(nums.begin(), nums.begin() + nums.size() / 2, nums.end());
        int avg = nums[nums.size() / 2];
        int ans = 0;
        for (auto &x : nums)
            ans += abs(x - avg);
        return ans;
    }
};