3736. 最小操作次数使数组元素相等 III
网页链接
力扣LeetCode
力扣LeetCode & 每日一题，完成每日打卡，即可获得力扣积分。获得相应数量的积分，能在【力扣商店】，换取相应奖品！助力每日有题做，丰盈积分日益多！
题目描述
给你一个整数数组nums。
在一步操作中，你可以将任意单个元素nums[i]的值增加 1。
返回使数组中的所有元素都相等所需的最小总操作次数。
输入描述
一个整数数组nums。
输出描述
返回使数组中的所有元素都相等所需的最小总操作次数。
示例
示例 1
输入：
nums = [2,1,3]输出：
3解释：
使所有元素相等的操作如下：
- 将
nums[0] = 2增加 1，变为 3。 - 将
nums[1] = 1增加 1，变为 2。 - 将
nums[1] = 2增加 1，变为 3。
现在，nums中的所有元素都等于 3。最小总操作次数为 3。
示例 2
输入：
nums = [4,4,5]输出：
2解释：
使所有元素相等的操作如下：
- 将
nums[0] = 4增加 1，变为 5。 - 将
nums[1] = 4增加 1，变为 5。
现在，nums中的所有元素都等于 5。最小总操作次数为 2。
数据范围
- 1 ≤ nums.length ≤ 100 1 \le \text{nums.length} \le 1001≤nums.length≤100
- 1 ≤ nums [ i ] ≤ 100 1 \le \text{nums}[i] \le 1001≤nums[i]≤100
解题思路
本题是贪心目标值选择 + 差值求和问题。每次操作只能将某个元素增加1，不能减少。因此最终所有元素相等时，目标值不可能小于数组当前的最大值；否则最大值元素无法通过“增加”变成更小的值。所以最优目标值就是数组的最大值。
1. 为什么目标值取最大值
设数组最大值为：
M = max ( n u m s ) M=\max(nums)M=max(nums)
由于只能对元素做加1操作：
- 若最终目标值小于
M，则当前最大元素M无法降低到目标值，不可行； - 若最终目标值大于
M，则所有元素都需要继续增加，操作次数只会更多； - 因此目标值取
M时最优。
2. 计算最少操作次数
对于任意元素nums[i]，要变成M，需要增加：
M − n u m s [ i ] M - nums[i]M−nums[i]
次。把所有元素的增加次数累加，得到总操作次数：
∑ i = 0 n − 1 ( M − n u m s [ i ] ) \sum_{i=0}^{n-1} \bigl(M - nums[i]\bigr)i=0∑n−1(M−nums[i])
化简得：
n × M − ∑ i = 0 n − 1 n u m s [ i ] n \times M - \sum_{i=0}^{n-1} nums[i]n×M−i=0∑n−1nums[i]
代码正是按这个公式计算：
returnranges::max(a)*a.size()-reduce(a.begin(),a.end(),0);其中：
ranges::max(a)求数组最大值M；a.size()是数组长度n；reduce(a.begin(), a.end(), 0)求数组元素总和。
3. 示例验证
对于nums = [2,1,3]：
- 最大值
M = 3； - 总和为
2 + 1 + 3 = 6； - 答案为：
3 × 3 − 6 = 3 3 \times 3 - 6 = 33×3−6=3
与示例输出一致。
对于nums = [4,4,5]：
- 最大值
M = 5； - 总和为
4 + 4 + 5 = 13； - 答案为：
3 × 5 − 13 = 2 3 \times 5 - 13 = 23×5−13=2
与示例输出一致。
4. 复杂度分析
- 求最大值：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 × max ( n u m s ) − ∑ n u m s [ i ] n \times \max(nums) - \sum nums[i]n×max(nums)−∑nums[i]
即最大值乘以数组长度，再减去数组元素总和。整体只需一次线性扫描，时间复杂度为O ( n ) O(n)O(n)。
代码内容
classSolution{public:intminMoves(vector<int>&a){returnranges::max(a)*a.size()-reduce(a.begin(),a.end(),0);}}; cannot be called from a running event loop：在 async 函数里该怎么改)
