462. 最小操作次数使数组元素相等 II

462.最小操作次数使数组元素相等

题目描述：

给你一个长度为 n 的整数数组 nums ，返回使所有数组元素相等需要的最小操作数。

在一次操作中，你可以使数组中的一个元素加 1 或者减 1 。

数据范围：

$1\le n \le 10^5$

题解：

首先排序，然后考虑最终全为 $x$ ，则 $x$ 肯定会在 $nums[0], nums[n - 1]$ 之间。

在 $nums[0], nums[n - 1]$ 之间时，代价为 $nums[n - 1] - nums[0]$ ，在 $nums[0], nums[n -1]$ 之外时，代价为 $nums[n - 1] - nums[0] + 2 \times (nums[0] - x)$ 。

因为 $nums[0],nums[n -1]$ 代价固定，因此可以直接抛弃这两个，看剩余的，同样的做法，最后会只剩 $nums[n/2]$ 或剩 $nums[n/2], nums[n/2 + 1]$ 。所以 $x$ 为 $[nums[n/2],nums[n/2]]$ 之间或 $[nums[n/2], nums[n/2 + 1]]$ 之间。又因为在区间内部时，代价是固定的，因此可以直接认为 $x$ 是 $nums[n/2]$ 。

代码：

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