Leetcode.453 最小操作次数使数组元素相等

题目链接

Leetcode.453 最小操作次数使数组元素相等 mid

题目描述

给你一个长度为 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<=1051 <= nums.length <= 10^51<=nums.length<=105
• −109<=nums[i]<=109-10^9 <= nums[i] <= 10^9−109<=nums[i]<=109
• 答案保证符合 32-bit 整数

解法：脑筋急转弯

我们要求的是让数组中所有元素相等的最小步数。

我们并不需要求出实际的所有元素相等时的元素值。

我们将 n - 1个元素增加 1 等价转换为 1个元素减少 1。

这样的话让所有元素相等的最小步数就是 每个元素减去最小元素之和。

∑i=0n−1nums[i]−min(nums)\\sum_{i = 0}^{n - 1}nums[i] - min(nums)∑i=0n−1​nums[i]−min(nums)

时间复杂度：$O(n)$

C++代码：

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

Python代码：

class Solution:def minMoves(self, nums: List[int]) -> int:minVal = min(nums)ans = 0for x in nums:ans = ans + (x - minVal)return ans