题目
给你一个长度为 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
代码实现
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;
}
public void swap(int[] nums, int index1, int index2) {
int temp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = temp;
}
}