Medium

题目描述

给你一个整数数组 nums。每次操作中，你可以选择数组中的一个下标 i（其中 0 <= i < nums.length），并将 nums[i] 的值增加 1。

请你返回使数组中的每个值都是唯一的所需的最少操作次数。

题目数据保证答案在 32 位整数范围内。

示例 1：

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

示例 2：

输入：nums = [3,2,1,2,1,7]
输出：6
解释：经过 6 次操作，数组可以变为 [3, 4, 1, 2, 5, 7]。
可以证明无法通过少于 6 次操作使数组的所有值都唯一。

提示：

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

解题思路

解题思路

这道题要求将数组中重复的数字通过增量操作变为唯一值，目标是使用最少的操作次数。

方法一：排序 + 贪心（推荐）

最直观的思路是排序后贪心处理：

  1. 将数组排序，这样相同的数字会聚集在一起
  2. 从左到右遍历，如果当前数字小于等于前一个数字，则将其增加到前一个数字+1
  3. 累计所有的增量操作次数

这样保证了每个位置的数字都严格大于前面的数字，从而实现唯一性。

方法二：计数排序

由于数组值的范围有限（0 ≤ nums[i] ≤ 10^5），也可以使用计数数组：

  1. 统计每个数字出现的次数
  2. 从小到大遍历，如果某个数字出现多次，将多余的部分依次分配到后面的位置

排序方法更容易理解和实现，时间复杂度相同，是推荐的解法。

代码实现

class Solution {
public:
    int minIncrementForUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int moves = 0;
        
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] <= nums[i-1]) {
                int increment = nums[i-1] + 1 - nums[i];
                moves += increment;
                nums[i] = nums[i-1] + 1;
            }
        }
        
        return moves;
    }
};

class Solution:
    def minIncrementForUnique(self, nums: List[int]) -> int:
        nums.sort()
        moves = 0
        
        for i in range(1, len(nums)):
            if nums[i] <= nums[i-1]:
                increment = nums[i-1] + 1 - nums[i]
                moves += increment
                nums[i] = nums[i-1] + 1
        
        return moves

public class Solution {
    public int MinIncrementForUnique(int[] nums) {
        Array.Sort(nums);
        int moves = 0;
        
        for (int i = 1; i < nums.Length; i++) {
            if (nums[i] <= nums[i-1]) {
                int increment = nums[i-1] + 1 - nums[i];
                moves += increment;
                nums[i] = nums[i-1] + 1;
            }
        }
        
        return moves;
    }
}

var minIncrementForUnique = function(nums) {
    nums.sort((a, b) => a - b);
    let moves = 0;
    
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] <= nums[i-1]) {
            const increment = nums[i-1] + 1 - nums[i];
            moves += increment;
            nums[i] = nums[i-1] + 1;
        }
    }
    
    return moves;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型排序方法
时间复杂度O(n log n)
空间复杂度O(1)

其中 n 是数组的长度。时间复杂度主要由排序操作决定，空间复杂度为常数级别（不考虑排序算法的额外空间）。

相关题目