LeetCode_贪心算法_中等_945.使数组唯一的最小增量

1.题目

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

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

示例 1：
输入：nums = [1,2,2]
输出：1
解释：经过一次 move 操作，数组将变为 [1, 2, 3]。

示例 2：
输入：nums = [3,2,1,2,1,7]
输出：6
解释：经过 6 次 move 操作，数组将变为 [3, 4, 1, 2, 5, 7]。
可以看出 5 次或 5 次以下的 move 操作是不能让数组的每个值唯一的。

提示：
1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁵

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-increment-to-make-array-unique

2.思路

（1）排序 & 贪心算法
① 先对数组 nums 进行升序排序，并定义变量 res 来保存所需要的最少操作次数，初始值为 0；
② 从数组 nums 的第 2 个元素开始遍历（如果数组 nums 的长度等于 1，则无需遍历，最少操作次数为 0，直接返回 res 即可）：
1）如果 nums[i] > nums[i - 1]，那么无需任何操作；
2）如果 nums[i] <= nums[i - 1]，那么为了保证所需要的操作次数最少，此时可以将 nums[i] 增加为 nums[i - 1] + 1，所需的操作次数为 diff = nums[i - 1] - nums[i] + 1，即 res += diff。
③ 遍历结束后，直接返回 res 即可。

Q：既然已经对数组 nums 进行升序排序了，为什么还需要考虑 nums[i] < nums[i - 1] 的情况？
A：这里实际上针对的是数组中存在多个相同元素的情况，以 nums = [3, 2, 1, 2, 1, 7, 2] 为例，进行升序排序后有 nums = [1, 1, 2, 2, 2, 3, 7]，那么在遍历的过程中，当 i = 4 的这一轮遍历结束后，nums = [1, 2, 3, 4, 5, 3, 7]，此时的 nums[5] = 3 < nums[4] = 5，所以需要考虑该情况。

3.代码实现（Java）

//思路1————排序 & 贪心算法
class Solution {
    public int minIncrementForUnique(int[] nums) {
        int length = nums.length;
        //对数组 nums 进行升序排序
        Arrays.sort(nums);
        int res = 0;
        for (int i = 1; i < length; i++) {
            if (nums[i] <= nums[i - 1]) {
                int diff = nums[i - 1] - nums[i] + 1;
                res += diff;
                nums[i] += diff;
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17