LeetCode 462. 最小操作次数使数组元素相等 II题目思路每次操作可让某个元素 1 或 -1要让所有元素相等且操作次数最少。数学结论设目标值为 x总代价为f(x) Σ |nums[i] - x|这是关于 x 的凸函数最小值在数组的中位数处取得偶数长度时取中间两个之一都行结果相同。直观理解把数组排序后把两端元素向中间靠拢。每次同时移动一对 (nums[left], nums[right])让它们相遇的最优位置就是中位数——移动 nums[right] - nums[left] 次。所有配对代价之和恰好等于每个元素到中位数的距离之和。解法一排序取中位数推荐importjava.util.Arrays;classSolution{publicintminMoves2(int[]nums){Arrays.sort(nums);intmediannums[nums.length/2];intmoves0;for(intnum:nums){movesMath.abs(num-median);}returnmoves;}}解法二快速选择找中位数O(n) 平均importjava.util.concurrent.ThreadLocalRandom;classSolution{publicintminMoves2(int[]nums){intnnums.length;intmedianquickSelect(nums,0,n-1,n/2);intmoves0;for(intnum:nums){movesMath.abs(num-median);}returnmoves;}// 返回第 k 小元素0-indexedprivateintquickSelect(int[]nums,intleft,intright,intk){while(leftright){intpivotIdxleftThreadLocalRandom.current().nextInt(right-left1);// 把 pivot 换到 left 位置swap(nums,left,pivotIdx);intpivotnums[left];intileft,jright;// 双指针分区避免大量重复元素退化while(ij){while(ijnums[j]pivot)j--;nums[i]nums[j];while(ijnums[i]pivot)i;nums[j]nums[i];}nums[i]pivot;if(ik)returnnums[i];elseif(ik)lefti1;elserighti-1;}returnnums[left];}privatevoidswap(int[]nums,inti,intj){inttmpnums[i];nums[i]nums[j];nums[j]tmp;}}复杂度分析解法 时间复杂度 空间复杂度 适用场景排序取中位数 O(n log n) O(log n)排序栈空间 代码简洁实际足够快快速选择 平均 O(n)最坏 O(n²) O(1) 数据量大且追求线性时间示例验证示例 1nums [1,2,3]· 排序后中位数 2· 代价|1-2| |2-2| |3-2| 1 0 1 2 ✓示例 2nums [1,10,2,9]· 排序后 [1,2,9,10]中位数取 2 或 9 均可· 取 21 0 7 8 16取 98 7 0 1 16 ✓两者结果相同易混淆题对比题目 操作方式 结论462本题 可 1 或 -1 选中位数代价为距离和453. 最小操作次数使数组元素相等 只能 1一次加 n-1 个元素 选最小值代价为 Σ(nums[i] - min)注意 453 题的等价转化每次给 n-1 个元素 1等价于每次给 1 个元素 -1因此目标是让所有元素降到最小值。而本题允许双向操作因此取中位数最优。