给你一个长度为 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.length1 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^9
题目集合：
解法1 数学+排序
每次可以将一个数加一或者减一，使得所有数组元素相等。凭借直觉可知，将所有数组元素向中间靠拢，所需要的操作次数最少。下面进行证明。
假设数组元素都变成 x x x 时，所需的移动数最少，那么 x x x 需要满足什么性质呢？
为了简化讨论，我们先假定数组长度 n n n 是偶数。我们将数组 nums \textit{nums} nums 从小到大进行排序，然后将数组进行首尾配对，从而划分为多个数对，并将这些数对组成区间： [ nums 0 , nums n − 1 ] , [ nums 1 , nums n − 2 ] , . . . , [ nums n 2 − 1 , nums n 2 ] [\textit{nums}_0, \textit{nums}_{n-1}], [\textit{nums}_1, \textit{nums}_{n-2}], ...,[\textit{nums}_{\frac{n}{2} - 1}, \textit{nums}_{\frac{n}{2}}] [nums0,numsn−1],[nums1,numsn−2],...,[nums2n−1,nums2n]
结论：当 x x x 同时位于以上区间内时，所需的移动数最少，总移动数为 ∑ i = 0 n 2 − 1 ( nums n − 1 − i − nums i ) \sum_{i=0}^{\frac{n}{2} - 1} (\textit{nums}_{n-1-i} - \textit{nums}_i) i=0∑2n−1(numsn−1−i−numsi)
当 n n n 为奇数时，我们将排序后的数组中间的元素 nums ⌊ n 2 ⌋ \textit{nums}_{\lfloor \frac{n}{2} \rfloor} nums⌊2n⌋ 当成区间 [ nums ⌊ n 2 ⌋ , nums ⌊ n 2 ⌋ ] [\textit{nums}_{\lfloor \frac{n}{2} \rfloor}, \textit{nums}_{\lfloor \frac{n}{2} \rfloor}] [nums⌊2n⌋,nums⌊2n⌋] 看待，则 x ∈ [ nums ⌊ n 2 ⌋ , nums ⌊ n 2 ⌋ ] x \in [\textit{nums}_{\lfloor \frac{n}{2} \rfloor}, \textit{nums}_{\lfloor \frac{n}{2} \rfloor}] x∈[nums⌊2n⌋,nums⌊2n⌋] 即 x = nums ⌊ n 2 ⌋ x= \textit{nums}_{\lfloor \frac{n}{2} \rfloor} x=nums⌊2n⌋ 时，所需的移动数最少。
综上所述，所有元素都变成 nums ⌊ n 2 ⌋ \textit{nums}_{\lfloor \frac{n}{2} \rfloor} nums⌊2n⌋ 时，所需的移动数最少。
class Solution {
public:
int minMoves2(vector<int>& nums) {
sort(nums.begin(), nums.end());
int n = nums.size(), ans = 0, x = nums[n / 2];
for (int i = 0; i < n; ++i) ans += abs(nums[i] - x);
// int i = 0, j = nums.size() - 1, ans = 0;
// while (i < j) ans += nums[j--] + nums[i++];
return ans;
}
};
复杂度分析：
- 时间复杂度： O ( n log n ) O(n\log n) O(nlogn)，其中 n n n 是数组 nums \textit{nums} nums 的长度。排序需要 O ( n log n ) O(n\log n) O(nlogn) 的时间。
- 空间复杂度： O ( log n ) O(\log n) O(logn) 。排序需要 O ( log n ) O(\log n) O(logn) 的递归栈空间。
解法2 快速选择
根据方法一的推导， x x x 取数组 nums \textit{nums} nums 第 ⌊ n 2 ⌋ \lfloor \frac{n}{2} \rfloor ⌊2n⌋ 小元素（从 0 0 0 开始计数）时，所需要的移动数最少。求解数组第 k k k 小元素可以使用快速选择算法。
class Solution {
public:
int quickSelect(vector<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);
}
}
inline int randomPartition(vector<int>& nums, int left, int right) {
int i = rand() % (right - left + 1) + left;
swap(nums[i], nums[right]);
return partition(nums, left, right);
}
inline int partition(vector<int>& nums, int left, int right) {
int x = nums[right], i = left - 1;
for (int j = left; j < right; ++j) {
if (nums[j] <= x) {
swap(nums[++i], nums[j]);
}
}
swap(nums[i + 1], nums[right]);
return i + 1;
}
int minMoves2(vector<int>& nums) {
srand(time(0));
int n = nums.size(), x = quickSelect(nums, 0, n - 1, n / 2), ret = 0;
for (int i = 0; i < n; ++i) {
ret += abs(nums[i] - x);
}
return ret;
}
};
复杂度分析：
- 时间复杂度： O ( n ) O(n) O(n) ，其中 n n n 是数组 nums \textit{nums} nums 的长度。快速选择算法的平均时间复杂度为 O ( n ) O(n) O(n) 。
- 空间复杂度： O ( log n ) O(\log n) O(logn) 。递归栈的平均占用空间为 O ( log n ) O(\log n) O(logn) 。