3736. 使数组元素相等的最少移动次数 III

Easy

题目描述

给定一个整数数组 nums。

在一次移动中，你可以将任意单个元素 nums[i] 的值增加 1。

返回使数组中所有元素相等所需的最少移动总次数。

示例 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 <= nums[i] <= 100

提示：

• 要使所有数字相等，它们必须都达到数组中的最大值。

解题思路

这道题的关键在于理解我们只能增加元素值，不能减少。因此，要使所有元素相等，最终的目标值必须是数组中的最大值。

思路分析：

由于我们只能增加元素的值，所以最终所有元素都必须等于数组中的最大值。任何小于最大值的尝试都是不可行的，因为我们无法将较大的元素减小。

算法步骤：

1. 找到数组中的最大值 maxVal
2. 遍历数组，计算每个元素与最大值的差值
3. 所有差值的总和就是所需的最少移动次数

数学原理： 对于数组中的每个元素 nums[i]，需要 maxVal - nums[i] 次移动才能将其增加到最大值。因此总移动次数为：

∑(maxVal - nums[i]) = n × maxVal - ∑nums[i]

其中 n 是数组长度。

这个解法的时间复杂度为 O(n)，空间复杂度为 O(1)，是最优解。

代码实现

class Solution {
public:
    int minMoves(vector<int>& nums) {
        int maxVal = *max_element(nums.begin(), nums.end());
        int moves = 0;
        for (int num : nums) {
            moves += maxVal - num;
        }
        return moves;
    }
};

class Solution:
    def minMoves(self, nums: List[int]) -> int:
        max_val = max(nums)
        return sum(max_val - num for num in nums)

public class Solution {
    public int MinMoves(int[] nums) {
        int maxVal = nums.Max();
        int moves = 0;
        foreach (int num in nums) {
            moves += maxVal - num;
        }
        return moves;
    }
}

var minMoves = function(nums) {
    const maxVal = Math.max(...nums);
    return nums.reduce((moves, num) => moves + (maxVal - num), 0);
};

复杂度分析