给你一个长度为 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 <= 105
-109 <= nums[i] <= 109
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/minimum-moves-to-equal-array-elements-ii
(1)中位数
① 先对数组 nums 进行排序;
② 求出排序后的数组 nums 的中位数 median;
③ 使所有数组元素相等需要的最少移动数就等于数组 nums 的所有元素与 median 的差的绝对值之和。
至于为什么选择中位数,可以参考该 LeetCode 用户题解。
(2)快速选择
有关快速选择的具体细节可以参考LeetCode_排序_快速选择_中等_215.数组中的第K个最大元素这篇文章。
相关题目:
LeetCode_逆向思维_中等_453.最小操作次数使数组元素相等
//思路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;
}
}
//思路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;
}
}