462. 最小操作次数使数组元素相等 II
网页链接
力扣LeetCode
力扣LeetCode & 每日一题，完成每日打卡，即可获得力扣积分。获得相应数量的积分，能在【力扣商店】，换取相应奖品！助力每日有题做，丰盈积分日益多！
题目描述
给你一个长度为n的整数数组nums，返回使所有数组元素相等需要的最小操作数。
在一次操作中，你可以使数组中的一个元素加1或者减1。
测试用例经过设计，以使答案在32 位整数范围内。
输入描述
一个长度为n的整数数组nums。
输出描述
返回使所有数组元素相等需要的最小操作数。
示例
示例 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 5 1 \le \text{nums.length} \le 10^51≤nums.length≤105
- − 10 9 ≤ nums [ i ] ≤ 10 9 -10^9 \le \text{nums}[i] \le 10^9−109≤nums[i]≤109
解题思路
本题是中位数贪心 + 快速选择问题。每次操作可以让一个元素加1或减1，目标是让所有元素相等，求最小总操作次数。因为总操作次数等于每个元素到最终目标值的绝对距离之和，所以问题转化为：
选择一个目标值
x，使得
[
\sum_i |nums[i]-x|
]
最小。
1. 为什么中位数最优
将数组排序后，设目标值为x。对于任意一个元素，它移动到x的代价是|nums[i]-x|。绝对值函数是凸函数，所有绝对值之和也在中位数处取得最小值。
直观理解：
- 若
x小于中位数，则右侧有更多元素需要向左移动，增大x可以减少总距离； - 若
x大于中位数，则左侧有更多元素需要向右移动，减小x可以减少总距离； - 因此最优目标值一定可以取数组的中位数。
当n为奇数时，中位数唯一；当n为偶数时，中间两个数之间的任意值都最优，代码取下标n/2对应的下中位数即可。
2. 快速选择找中位数
如果直接排序，需要O ( n log n ) O(n\log n)O(nlogn)时间。本题只需要找到第n/2小的元素，因此可以使用快速选择算法，期望时间复杂度为O ( n ) O(n)O(n)。
代码中：
qs(a, l, r, k)：在区间[l, r]中寻找第k小元素；rp(a, l, r)：随机选择枢轴，并将它交换到区间末尾；pt(a, l, r)：以末尾元素为枢轴进行划分，返回枢轴最终位置。
划分后：
- 若枢轴位置
p == k，说明a[p]就是第k小元素； - 若
p < k，目标在右半区间，递归qs(a, p+1, r, k)； - 若
p > k，目标在左半区间，递归qs(a, l, p-1, k)。
最终得到的x = qs(a, 0, n-1, n/2)就是中位数。
3. 计算最小操作次数
找到中位数x后，遍历数组，累加每个元素到x的绝对距离：
r+=abs(a[i]-x);该累加值就是使所有元素都变成x所需的最少操作次数，也就是本题答案。
4. 随机化的作用
快速选择的最坏情况是O ( n 2 ) O(n^2)O(n2)。代码通过rand()随机选择枢轴，避免在特殊数据（如已排序数组）上反复出现极不平衡划分。随机化后，期望时间复杂度为O ( n ) O(n)O(n)。
5. 复杂度分析
- 期望时间复杂度：O ( n ) O(n)O(n)，快速选择平均每次将问题规模缩小约一半；
- 最坏时间复杂度：O ( n 2 ) O(n^2)O(n2)，但随机化后实际几乎不会出现；
- 空间复杂度：递归栈期望O ( log n ) O(\log n)O(logn)，最坏O ( n ) O(n)O(n)；额外数组空间为O ( 1 ) O(1)O(1)。
总结
所有元素到目标值的绝对距离之和在中位数处最小。因此先用随机快速选择在O ( n ) O(n)O(n)期望时间内找到中位数，再遍历数组累加每个元素与中位数的绝对差，即为最少操作次数。该方法避免了完整排序，效率更高。
代码内容
classSolution{public:intqs(vector<int>&a,intl,intr,intk){intp=rp(a,l,r);if(p==k){returna[p];}returnp<k?qs(a,p+1,r,k):qs(a,l,p-1,k);}inlineintrp(vector<int>&a,intl,intr){inti=rand()%(r-l+1)+l;swap(a[i],a[r]);returnpt(a,l,r);}inlineintpt(vector<int>&a,intl,intr){intx=a[r],i=l-1;for(intj=l;j<r;++j){if(a[j]<=x){swap(a[++i],a[j]);}}swap(a[i+1],a[r]);returni+1;}intminMoves2(vector<int>&a){srand(time(0));intn=a.size(),x=qs(a,0,n-1,n/2),r=0;for(inti=0;i<n;++i){r+=abs(a[i]-x);}returnr;}};
