462. Minimum Moves to Equal Array Elements II

Leetcode link

解题思路

题目要求我们将一个数组中的数字使用最少的操作变成全部一样

根据题目描述，我们要找的肯定是所有数字的中位数了，所以我们只需要对数组排序之后，将每个数字都与中位数相减之后加总就是解答了

Javascript

/**
 * @param {number[]} nums
 * @return {number}
 */
var minMoves2 = function(nums) {
    nums.sort((a, b)=>a-b);
    let mid = nums[Math.floor(nums.length / 2)]
    let res = 0;
    for(let num of nums) {
        res+= Math.abs(num - mid);
    }
    return res;
};

本题的性能优化点在排序算法的使用上，在 215 中，我们对快速排序做了一个改进，使其可以在 O(n) 的复杂度下求解出第 k 小的元素，这一题的思路只是把 215 的第 k 小变成第 num.lenth / 2 小罢了，具体可以参考 215 的代码