462. 最少移动次数使数组元素相等 II

1.题目

给你一个长度为 n 的整数数组 nums ，返回使所有数组元素相等需要的最少移动数。
在一步操作中，你可以使数组中的一个元素加 1 或者减 1 。

输入：nums = [1,2,3]
输出：2
解释：
只需要两步操作（每步操作指南使一个元素加 1 或减 1）：
[1,2,3]  =>  [2,2,3]  =>  [2,2,2]
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-moves-to-equal-array-elements-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

输入：nums = [1,10,2,9]
输出：16

提示：

• n == nums.length
• 1 <= nums.length <= 105
• -109 <= nums[i] <= 109

  2.思路

  1）自己的直觉

  将数值转化为数轴上的点后，这个问题就变成了给定一群数轴上的点，求在数轴上找另一个点使得这群点到这点的距离之和最小。嗯，直觉就是取这群点的中位点，然后求距离之和。

  2）题解

  当数组个数为偶数时，最大最小，次最大次最小两两组合就可以，对于我们要选定的数x来说（这里x取两数之内的结果要优于取两数之外的结果，请画图理解）|num1-x|+|num2-x|>=|num1-num2|，所以只要x取这些成对的组公有的值时就可以取得最小值。而当x为基数时，对于单个的数num[n/2]构造（num[n/2]，num[n/2]）这时x就为num[n/2]。

  3.代码

  class Solution {
  public:
    int minMoves2(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size(), ans = 0;
        int mid = n%2? nums[n/2]:(nums[n/2-1]+nums[n/2])/2;//mid也可直接取num[n/2]
        for(int i = 0; i < n; i++)
        {
            ans = ans + abs(nums[i]-mid);
        }
        return ans;
    }
  };