题目描述

给定一个数组，都是整数。
给定一种操作，每次能够使得数组中的任意一个数加一或者减一。
问最少多少次操作能够使得数组中的元素大小相等。

样例

输入
[1,2,3]

输出
2

算法

(数学) $O(nlog(n))$

对于整个数组排序。
想象数组中的每一个数都在数轴上，最终我们数组中的值为x.
那么所需要求解的就是数组中的每一个数到达x的距离和最小。
根据绝对值不等式我们知道，当且仅当x处于数组的中间时，所求值最小。

时间复杂度：由于采用的排序,所以复杂度是 $O(nlog(n))$

C++ 代码

class Solution {
public:
    int minMoves2(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int num = nums[nums.size()/2];
        int res = 0;
        for (int i = 0;i<nums.size();++i){
            res += abs(num-nums[i]);

        }

        return res;
    }
};