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 个元素。

自建示例

三个不同元素:

输入: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)。