0945.md

title	description	keywords
945. 使数组唯一的最小增量	LeetCode 945. 使数组唯一的最小增量题解，Minimum Increment to Make Array Unique，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。	LeetCode 945. 使数组唯一的最小增量 使数组唯一的最小增量 Minimum Increment to Make Array Unique 解题思路 贪心 数组 计数 排序

945. 使数组唯一的最小增量

🟠 Medium  🔖  贪心 数组 计数 排序  🔗 力扣 LeetCode

题目

You are given an integer array nums. In one move, you can pick an index i where 0 <= i < nums.length and increment nums[i] by 1.

Return the minimum number of moves to make every value innums unique.

The test cases are generated so that the answer fits in a 32-bit integer.

Example 1:

Input: nums = [1,2,2]

Output: 1

Explanation: After 1 move, the array could be [1, 2, 3].

Example 2:

Input: nums = [3,2,1,2,1,7]

Output: 6

Explanation: After 6 moves, the array could be [3, 4, 1, 2, 5, 7].

It can be shown with 5 or less moves that it is impossible for the array to have all unique values.

Constraints:

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^5

题目大意

给你一个整数数组 nums 。每次 move 操作将会选择任意一个满足 0 <= i < nums.length 的下标 i，并将 nums[i] 递增 1。

返回使 nums 中的每个值都变成唯一的所需要的最少操作次数。

生成的测试用例保证答案在 32 位整数范围内。

解题思路

为了确保数组中的所有元素都是唯一的，并且操作次数最少，关键思想是先对数组进行排序。通过排序，可以从最小值到最大值以线性扫描的方式处理重复项。这样，对于每个元素，可以直接将其移动到下一个可用的唯一位置，从而最小化所需的总增量。

1. 对数组进行排序：排序有助于识别重复项并确定每个元素的下一个可用唯一位置。
2. 初始化变量：使用两个变量 i 和 res，i 表示下一个唯一数字所需的当前最小值，res 跟踪所做的总操作次数。
3. 遍历数组：对于排序数组中的每个元素：
   • 将 i 更新为其当前值和当前元素值中的最大值，这可确保 i 始终是使元素唯一的最小值。
   • 将 res 增加 i 和当前元素之间的差值，此差值表示使当前元素唯一所需的操作次数。
   • 增加 i 以移动到下一次迭代的下一个可能唯一值。
4. 返回结果：返回使所有元素唯一所需的增量总数 res。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var minIncrementForUnique = function (nums) {
	nums.sort((a, b) => a - b);
	let i = 0,
		res = 0;
	for (let num of nums) {
		i = Math.max(i, num);
		res += i - num;
		i++;
	}
	return res;
};

相关题目

题号	标题	题解	标签	难度	力扣
1827	最少操作使数组递增	[✓]	贪心 数组	🟢	🀄️ 🔗
2233	K 次增加后的最大乘积		贪心 数组 堆（优先队列）	🟠	🀄️ 🔗