Leetcode-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 <= 10e5
• -10e9 <= nums[i] <= 10e9

思路

很容易想到，先对数组进行排序，往最小的值移动必然不可能，而往最大的值移动也必然不可能，必须是左右两边一起往中间移动，而且是要往最中间的位置移动，那么就是均值、中位数这些特殊的值，测试均值发现有问题，再测试中位数成功AC。

Java Code

class Solution {
    /*均值
    public int minMoves2(int[] nums) {
        int res1 = 0;
        int res2 = 0;
        int sum = 0;
        int n = nums.length;
        for(int i=0;i
            sum+=nums[i];
        }
        int ave1 = sum/n;
        int ave2 = sum/n + 1;
        for(int i=0;i
            res1+=Math.abs(nums[i]-ave1);
            res2+=Math.abs(nums[i]-ave2);
        }
        return Math.min(res1,res2);
    }*/
 
    //中位数
    public int minMoves2(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length, t = nums[(n - 1) / 2], ans = 0;
        for (int i : nums) ans += Math.abs(t - i);
        return ans;
    }
 
 
 
}