LeetCode_排序_快速选择_中等_462.最少移动次数使数组元素相等 II

1.题目

给你一个长度为 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⁵
-109 <= nums[i] <= 10⁹

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-moves-to-equal-array-elements-ii

2.思路

（1）中位数
① 先对数组 nums 进行排序；
② 求出排序后的数组 nums 的中位数 median；
③ 使所有数组元素相等需要的最少移动数就等于数组 nums 的所有元素与 median 的差的绝对值之和。

至于为什么选择中位数，可以参考该 LeetCode 用户题解。

（2）快速选择
有关快速选择的具体细节可以参考LeetCode_排序_快速选择_中等_215.数组中的第K个最大元素这篇文章。

相关题目：
LeetCode_逆向思维_中等_453.最小操作次数使数组元素相等

3.代码实现（Java）

//思路1————中位数
class Solution {
    public int minMoves2(int[] nums) {
        int res = 0;
        int n = nums.length;
        Arrays.sort(nums);
        /* 
        	median 为排序后的数组 nums 的中位数，需要注意的是，这里所求的中位数必须是整数
            (1) 如果数组 nums 的长度是奇数时，中位数就是 nums[n / 2]
            (2) 如果数组 nums 的长度是偶数时，按照原来的计算公式 (nums[n / 2] + nums[n / 2 - 1]) / 2.0 
            求出的答案可能不是整数，所以还需要对其做向下取整的操作，最后的结果正好就是 nums[n / 2]
		*/
        int median = nums[n / 2];
        for (int num : nums) {
            res += Math.abs(num - median);
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

//思路2————快速选择
class Solution {
    Random random = new Random();
    
    public int minMoves2(int[] nums) {
        int n = nums.length, x = quickSelect(nums, 0, n - 1, n / 2), ret = 0;
        for (int i = 0; i < n; ++i) {
            ret += Math.abs(nums[i] - x);
        }
        return ret;
    }
    
    public int quickSelect(int[] nums, int left, int right, int index) {
        int q = randomPartition(nums, left, right);
        if (q == index) {
            return nums[q];
        } else {
            return q < index ? quickSelect(nums, q + 1, right, index) : quickSelect(nums, left, q - 1, index);
        }
    }
    
    public int randomPartition(int[] nums, int left, int right) {
        int i = random.nextInt(right - left + 1) + left;
        swap(nums, i, right);
        return partition(nums, left, right);
    }
    
    public int partition(int[] nums, int left, int right) {
        int x = nums[right], i = left - 1;
        for (int j = left; j < right; ++j) {
            if (nums[j] <= x) {
                ++i;
                swap(nums, i, j);
            }
        }
        swap(nums, i + 1, right);
        return i + 1;
    }
    
    //交换 nums[i] 和 nums[j] 的值
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46