453. 最小操作次数使数组元素相等
题目描述
输入长度为 n 的整数数组 nums。
一次操作可以任选 n - 1 个元素，把它们各自加 1。
返回让数组中所有元素变得相等所需的最少操作次数。
示例 1
输入：nums = [1,2,3] 输出：3
解释：[1,2,3] 依次变为 [2,3,3]、[3,4,3]、[4,4,4]，共 3 次。
示例 2
输入：nums = [1,1,1] 输出：0
解释：元素已经相等，不需要操作。
数据范围
n == nums.length1 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^9- 答案在 32 位整数范围内。
解题思路
关键是换个角度：让 n - 1 个数加 1，与让剩下那 1 个数减 1，对“元素之间的相对差”效果完全一样。所以问题等价于每次把某一个数减 1，直到全部相等。减法只会让数变小，最省的目标就是最小值 lo，每个数要减 x - lo 次，总次数是它们之和。
为什么正确
任何一次操作都使某个元素相对其他元素下降 1；所有相对差归零所需次数恰为 sum(x - lo)。
复杂度分析
时间 O(n)，额外空间 O(1)。
易错点
直接模拟“每次给最小的 n-1 个数加 1”会超时；另外要以最小值而不是平均值为目标，因为等价操作只能让数变小。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def minMoves(self, nums: List[int]) -> int:
lo = min(nums)
moves = 0
for x in nums:
moves += x - lo
return movesclass Solution {
public int minMoves(int[] nums) {
int lo = Arrays.stream(nums).min().getAsInt();
int moves = 0;
for (int x : nums) {
moves += x - lo;
}
return moves;
}
}class Solution {
public:
int minMoves(vector<int>& nums) {
int lo = *min_element(nums.begin(), nums.end());
int moves = 0;
for (int x : nums) {
moves += x - lo;
}
return moves;
}
};func minMoves(nums []int) int {
lo := slices.Min(nums)
moves := 0
for _, x := range nums {
moves += x - lo
}
return moves
}var minMoves = function(nums) {
const lo = Math.min(...nums);
let moves = 0;
for (const x of nums) {
moves += x - lo;
}
return moves;
};function minMoves(nums: number[]): number {
const lo = Math.min(...nums);
let moves = 0;
for (const x of nums) {
moves += x - lo;
}
return moves;
}