本文共 1038 字，大约阅读时间需要 3 分钟。

为了使给定的整数数组中的每个值唯一，最少需要进行多少次操作？每次操作可以选择任意一个元素，将其递增1。

方法思路

为了解决这个问题，我们可以使用贪心算法。具体步骤如下：

这种方法的时间复杂度是 O(n log n)，主要是由于排序操作带来的。空间复杂度是 O(1)，因为我们只使用了额外的变量。

解决代码

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        if not A:
            return 0
        A.sort()
        preMax = 1
        count = 0
        for num in A:
            if num > preMax:
                count += num - preMax
                preMax = num + 1
            else:
                count += preMax - num
                preMax = num + 1
        return count

代码解释

• 排序数组：使用 A.sort() 对数组进行排序。
• 初始化变量：preMax 初始化为1，表示当前处理到的最大值。
• 遍历数组：对于每个元素 num，检查它是否大于 preMax。
  • 如果 num 大于 preMax，说明它需要移动到当前位置，计算移动次数并更新 preMax。
  • 如果 num 小于或等于 preMax，说明它需要移动到 preMax 的位置，计算移动次数并更新 preMax。
• 累计操作次数：将每次移动的次数累加到 count 中，最后返回总操作次数。

通过这种方法，我们可以高效地找到使数组中的每个值唯一的最少操作次数。