Medium

题目描述

给你一个长度为 n 的整数数组 nums，返回使数组所有元素相等所需的最少移动次数。

在一次移动中，你可以使数组中其中 n - 1 个元素各自加 1。

示例 1：

输入：nums = [1,2,3]
输出：3
解释：只需要3次移动（记住每次移动会增加两个元素的值）：
[1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]

示例 2：

输入：nums = [1,1,1]
输出：0

提示：

  • n == nums.length
  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • 答案保证在 32 位整数范围内。

解题思路

这道题的关键在于理解题意和找到数学规律。

思路分析：

首先理解操作规则：每次可以选择 n-1 个元素同时加1，相当于让剩下的那个元素相对减1。

核心洞察： 每次操作本质上是让某个元素相对于其他元素减少1。因此，要让所有元素相等，最优策略是让所有元素都"降低"到最小元素的值。

数学推导：

  • 设最小元素值为 min_val
  • 对于每个元素 nums[i]，需要进行 nums[i] - min_val 次操作来降低到最小值
  • 总移动次数就是所有元素与最小值的差值之和：sum(nums[i] - min_val)

验证示例1：

  • nums = [1,2,3]，min_val = 1
  • 移动次数 = (2-1) + (3-1) = 1 + 2 = 3

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

代码实现

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

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

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

var minMoves = function(nums) {
    const minVal = Math.min(...nums);
    return nums.reduce((moves, num) => moves + (num - minVal), 0);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历数组找最小值和计算总差值
空间复杂度O(1)只使用常量额外空间

相关题目