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

🟠   🔖  贪心 数组 计数 排序  🔗 力扣 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 innumsunique.

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 次增加后的最大乘积		贪心 数组 堆（优先队列）