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)``。