leetcode453：最小操作次数使数组元素相等

[wangyewei]

给你一个长度为 n 的整数数组，每次操作将会使 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 <= 105
-109 <= nums[i] <= 109
答案保证符合 32-bit 整数

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-moves-to-equal-array-elements

[wangyewei]

思路和算法

因为只需要找出让数组所有元素相等的最小操作次数，所以我们不需要考虑数组中各个元素的绝对大小，即不需要真正算出数组中所有元素相等时的元素值，只需要考虑数组中元素相对大小的变化即可。

因此，每次操作既可以理解为使 n-1个元素增加 1，也可以理解使 1 个元素减少 1。显然，后者更利于我们的计算。

于是，要计算让数组中所有元素相等的操作数，我们只需要计算将数组中所有元素都减少到数组中元素最小值所需的操作数，即计算

​

其中 n为数组 nums 的长度，min(nums)为数组 nums 中元素的最小值。

在实现中，为避免溢出，我们可以逐个累加每个元素与数组中元素最小值的差，即计算

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var minMoves = function(nums) {
    let operatingFrequency = 0
    let minNum = Math.min(...nums)
    for(const num of nums) {
        operatingFrequency += num - minNum
    }
    return operatingFrequency
};

复杂度分析

• 时间复杂度：O(n)，其中 n 为数组中的元素数量。需要一次遍历求出最小值，一次遍历计算操作次数。

• 空间复杂度：O(1)。