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

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

难度中等

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

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

示例 1：

输入：nums = [1,2,3]
输出：2
解释：
只需要两步操作（每步操作指南使一个元素加 1 或减 1）：
[1,2,3]  =>  [2,2,3]  =>  [2,2,2]

示例 2：

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

提示：

• n == nums.length
• 1 <= nums.length <= 10<sup>5</sup>
• -10<sup>9</sup> <= nums[i] <= 10<sup>9</sup>

思想及代码：

Code1：超时

class Solution {
    public:
        int minMoves2(vector<int> &nums) {
            int cnt = 0;
            sort(nums.begin(), nums.end());
            int pos = nums.size() / 2 - 1;
            int i = 0, j = nums.size() - 1;
            while (i < j) {
                while (nums[i] < nums[pos]) {
                    nums[i]++;
                    cnt++;
                }
                i++;
                while (nums[j] > nums[pos]) {
                    nums[j]--;
                    cnt++;
                }
                j--;
            }
            return cnt;
        }
};

Code2：双指针，时间优化

class Solution {
    public:
        int minMoves2(vector<int> &nums) {
            int cnt = 0;
            sort(nums.begin(), nums.end());
            int pos = (nums.size()-1)/2;
            int i = 0, j = nums.size() - 1;
            while (i < j) {
                int cnt1 = nums[pos] - nums[i];
                int cnt2 = nums[j] - nums[pos];
                cnt += cnt1+cnt2;
                i++; 
                j--;
            }
            return cnt;
        }
};

Code3：用数学原理再优化

两数相减的差即为这两个数变为相等的加减次数

class Solution {
    public:
        int minMoves2(vector<int> &nums) {
            int cnt = 0;
            sort(nums.begin(), nums.end());
            int i = 0, j = nums.size() - 1;
            while (i < j) {
                cnt += nums[j] - nums[i];
                ++i;
                --j;
            }
            return cnt;
        }
};