453. 最小操作次数使数组元素相等
网页链接
力扣LeetCode
力扣LeetCode & 每日一题，完成每日打卡，即可获得力扣积分。获得相应数量的积分，能在【力扣商店】，换取相应奖品！助力每日有题做，丰盈积分日益多！
题目描述
给你一个长度为n的整数数组，每次操作将会使n - 1个元素增加1。返回让数组所有元素相等的最小操作次数。
输入描述
一个长度为n的整数数组nums。
输出描述
返回让数组所有元素相等的最小操作次数。
示例
示例 1
输入：
nums = [1,2,3]输出：
3解释：
只需要3 33次操作（注意每次操作会增加两个元素的值）：
[1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]示例 2
输入：
nums = [1,1,1]输出：
0数据范围
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
- 答案保证符合32-bit整数
解题思路
本题是操作等价转化 + 相对差值求和问题。每次操作会把n - 1个元素同时加1，直接模拟操作次数会很多，也不方便。关键在于把“增加大多数元素”转化为“减少单个元素”。
1. 操作等价转化
每次操作选择n - 1个元素加1，等价于：
- 所有元素都加
1； - 再让未被选中的那个元素减
1。
由于“所有元素同时加1”不会改变任意两个元素之间的相对差值，也不会影响最终它们是否相等，因此可以忽略这个整体加1的部分。于是原操作等价于：
每次选择数组中的一个元素，将其减
1。
目标仍然是让所有元素相等。
2. 最终相等值只能是最小值
如果每次只能把某个元素减1，那么元素只能变小，不能变大。因此最终所有元素相等时，目标值不能大于数组中的最小值，否则原本的最小值无法通过“减1”达到更大的值。
所以最终相等值必然就是数组的最小值：
m = min ( n u m s ) m = \min(nums)m=min(nums)
3. 计算最少操作次数
对于任意元素nums[i]，要把它降到最小值m，需要的操作次数为：
n u m s [ i ] − m nums[i] - mnums[i]−m
每个元素都必须至少降到m，且降到m后不能再继续减小，否则会小于目标值。因此总操作次数为：
∑ i = 0 n − 1 ( n u m s [ i ] − m ) \sum_{i=0}^{n-1} \bigl(nums[i] - m\bigr)i=0∑n−1(nums[i]−m)
这正是代码中：
intm=*min_element(a.begin(),a.end());intr=0;for(intx:a){r+=x-m;}returnr;所计算的内容。
4. 示例验证
对于nums = [1,2,3]，最小值为1，答案为：
( 1 − 1 ) + ( 2 − 1 ) + ( 3 − 1 ) = 0 + 1 + 2 = 3 (1-1)+(2-1)+(3-1)=0+1+2=3(1−1)+(2−1)+(3−1)=0+1+2=3
与示例输出一致。
对于nums = [1,1,1]，最小值为1，答案为：
0 + 0 + 0 = 0 0+0+0=00+0+0=0
也与示例一致。
5. 复杂度分析
- 求最小值：O ( n ) O(n)O(n)；
- 遍历数组累加差值：O ( n ) O(n)O(n)；
- 总时间复杂度为O ( n ) O(n)O(n)；
- 只使用常数个额外变量，空间复杂度为O ( 1 ) O(1)O(1)。
总结
每次让n - 1个元素加1，等价于让一个元素减1。由于元素只能减小，最终所有元素只能变成数组的最小值。因此最少操作次数就是所有元素与最小值之差的总和，直接一次遍历累加即可。
代码内容
classSolution{public:intminMoves(vector<int>&a){intm=*min_element(a.begin(),a.end());intr=0;for(intx:a){r+=x-m;}returnr;}};