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