0462. Minimum Moves to Equal Array Elements II

---

Given an integer array nums of size n, return the minimum number of moves required to make all array elements equal.

In one move, you can increment or decrement an element of the array by 1.

Example 1:

Input: nums = [1,2,3]
Output: 2
Explanation:
Only two moves are needed (remember each move increments or decrements one element):
[1,2,3]  =>  [2,2,3]  =>  [2,2,2]

Example 2:

Input: nums = [1,10,2,9]
Output: 16

Constraints:

• n == nums.length
• 1 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9

---

解法1

就是要找到中间的点. 虽然无法给出证明, 但是在排序的情况下, 就是以中心点为基准.

其实这里有个小问题, 就是按照题目中的条件,其实结果是有可能会越界的.不过既然返回结果是int, 那就默认不会越界吧.

class Solution {
    public int minMoves2(int[] nums) {
        if(nums.length == 1)
            return 0;
        
        Arrays.sort(nums);
        int mid = nums[nums.length / 2];
        int res = 0;
        for(int num : nums){
            res += Math.abs(num - mid);
        }
        return res;
    }
}

---

解法2

当数据量非常大的时候, 可以自定义快速排序, 只需要找到中心点就可以, 而不用把数组完整排序. 这样可以把时间复杂度从O(N*logN) 减少到 O(N).

class Solution {
    public int minMoves2(int[] nums) {
        // 得到基准点
        int mid = getMid(nums);
        int res = 0;
        for(int num : nums)
            res += Math.abs(num - mid);

        return res;
    }
    
    private int getMid(int[] nums){
        int left = 0, right = nums.length - 1, target = right / 2;
        while(left < right){
            int temp = nums[left];
            int index = left + 1;
            for(int i = index; i <= right; i++){
                if(nums[i] > temp){
                    swap(nums, i, index);
                    index++;
                }
            }
            index--;
            swap(nums, left, index);
            if(index > target)
                right = index - 1;
            else if (index < target)
                left = index + 1;
            else 
                break;
        }
        return nums[target];
    }
    
    private void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}