0453. Minimum Moves to Equal Array Elements¶
题目信息¶
- 题号:
0453
- 难度:
Medium
- 主题:
整数数组、每次增加
n-1项、元素相等、最少操作- 原题:
- 重点:
一次操作必须选择除一个位置外的所有元素各加 1、目标是全部相等、返回操作次数
题目重述¶
给定整数数组 nums。一次操作可以选择数组中恰好 n-1 个元素,并把这些元素都增加 1。返回使数组所有元素相等所需的最少操作次数。
nums.length 位于 [1, 10^5],每个元素位于 [-10^9, 10^9],题目保证答案适合 32 位有符号整数。每次操作中未增加的那个位置可以不同;不能在一次操作中只增加少于 n-1 个元素。
自建示例¶
三个不同元素:
输入:nums = [2, 4, 6]
输出:6
解释:每次增加除一个元素外的所有元素,等价于每次把某一个元素减 1;把 4 和 6 分别降到最小值 2 共需 2 + 4 = 6 次。
只有一个元素:
输入:nums = [-7]
输出:0
解释:数组已经满足所有元素相等,不需要操作。
把一次操作换算成减少一个元素¶
一次操作给 n-1 个元素都加 1。若把“所有元素同时加 1”看成不改变相等关系的基准,那么该操作等价于只把被跳过的那个元素相对减少 1。为了让所有元素最终相等,最优基准是数组最小值:每个元素需要被相对减少 nums[i] - minimum 次,最小值本身不需要减少。
这个换算也解释了为什么不能直接模拟不断加法:实际数值可能很大,但相对差值每次只会减少一个单位,答案直接是差值总和。
C++ 实现¶
class Solution {
public:
int minMoves(std::vector<int>& nums) {
int minimum = *std::min_element(nums.begin(), nums.end());
long long moves = 0;
for (int value : nums) {
moves += static_cast<long long>(value) - minimum;
}
return static_cast<int>(moves);
}
};
代码分析¶
每次操作只改变一个元素相对于其余元素的差值,所有差值都必须至少减少到零;把每个元素降到全局最小值恰好达到这个下界,因此是最优方案。只需一次扫描求差值总和,时间复杂度为 O(n),额外空间复杂度为 O(1)。