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

🟠   🔖  数组 数学  🔗 力扣 LeetCode

题目

Given an integer array nums of size n, return the minimum number of moves required to make all array elements equal.

In one move, you can increment n - 1 elements of the array by 1.

Example 1:

Input: nums = [1,2,3]

Output: 3

Explanation: Only three moves are needed (remember each move increments two elements):

[1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]

Example 2:

Input: nums = [1,1,1]

Output: 0

Constraints:

• n == nums.length
• 1 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9
• The answer is guaranteed to fit in a 32-bit integer.

题目大意

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

解题思路

本题要求计算 将数组所有元素变成相等的最小移动次数。每次操作可以让 n-1 个元素加 1，等价于 让 1 个元素减 1，因此可以转化为 让所有元素减少到最小值的操作次数。

1. 定义目标值

   • 目标是让所有元素变成 数组最小值 min，因为减法操作（n-1 个数 +1 相当于 1 个数 -1）只能减少较大数值。

2. 计算需要的操作次数

   • 假设 sum 是数组所有元素的总和，len 是数组长度：

     • 最终每个元素值 = min(nums)
     • 总移动次数 = sum - (min(nums) * len)

   • 其中：

     • sum 是数组所有元素的和。
     • min * len 是所有元素都变成 min 之后的总和。
     • sum - min * len 代表所有元素 减少到 min 的操作总数。

复杂度分析

• 时间复杂度： O(n)，计算 min 和 sum 各 O(n)。
• 空间复杂度： O(1)，只使用常量额外变量 min 和 sum。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var minMoves = function (nums) {
	const min = Math.min(...nums); // 计算数组最小值
	const sum = nums.reduce((acc, cur) => acc + cur, 0); // 计算数组总和
	return sum - min * nums.length; // 计算最少操作次数
};

相关题目

题号	标题	题解	标签	难度	力扣
462	最小操作次数使数组元素相等 II	[✓]	数组 数学 排序	🟠	🀄️ 🔗
2137	通过倒水操作让所有的水桶所含水量相等 🔒		数组 二分查找	🟠	🀄️ 🔗
2141	同时运行 N 台电脑的最长时间		贪心 数组 二分查找 1+	🔴	🀄️ 🔗
2491	划分技能点相等的团队	[✓]	数组 哈希表 双指针 1+	🟠	🀄️ 🔗
3190	使所有元素都可以被 3 整除的最少操作数		数组 数学	🟢	🀄️ 🔗