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

不念不忘少年蓝@ 2023-10-06 23:58 13阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 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 <= 105  
0 <= nums\[i\] <= 105

来源：力扣（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;
        }
    }