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
2.思路
2.1 代码
题目要求找到每一位数字移动的最小次数，因此考虑先对数组进行排序，然后取中位数，再对每一位依次和中位数进行对比即可。这个时候便会遇到数组个数是奇数和偶数两种情况：
- 数组个数是奇数的话直接取最中间元素即可，即 mid = nums.length / 2 ；
- 数组个数是偶数的话中位数有两个，即最中间两位，这个时候取这两个任意一位均可，证明如下：
假设数组 。其中 n 为偶数，
和
为该有序数组的两个中位数。
如果选择 进行操作，在角标 mid-1 之前的都是比
小的，之后都是比
大的，因此得到移动次数：
同理可得选用 进行操作的结果：
从上面结果可以看出 和
相等。
代码如下：
class Solution {
public int minMoves2(int[] nums) {
if (nums.length == 2) {
return Math.abs(nums[0] - nums[1]);
}
Arrays.sort(nums);
int mid = nums.length / 2;
long ans1 = 0L;
for (int num : nums) {
ans1 += Math.abs(num - nums[mid]);
}
return (int) ans1;
}
}
2.2 测试结果
通过测试
测试结果
3.总结
- 先对数组进行排序，然后选择中位数进行移动操作
- 数组长度为奇数时，选择最中间的元素；数组长度为偶数时，中间两个选择任意一个都正确
