How do I approach the Minimum Increment to Make Array Unique problem?

Start by sorting the array. Then, increment each element as needed to ensure uniqueness, using a greedy strategy and tracking used values with a set.

What is the time complexity of solving the Minimum Increment to Make Array Unique problem?

The time complexity is O(n log n) due to the sorting step, followed by an O(n) greedy traversal. Space complexity is O(n + max), where max is the largest number in the array.

Can the Minimum Increment to Make Array Unique problem be solved without sorting?

Sorting is an essential part of the solution as it ensures that we can increment values in the smallest possible order, minimizing the total number of moves.

What are some common pitfalls in solving the Minimum Increment to Make Array Unique problem?

Key pitfalls include failing to sort the array first, inefficiently validating uniqueness, or not handling edge cases where no increments are needed.

How does the greedy approach apply to the Minimum Increment to Make Array Unique problem?

The greedy approach ensures that each element is incremented to the smallest possible value that maintains uniqueness, minimizing the total number of moves required.

#945

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

使数组唯一的最小增量

给你一个整数数组 nums 。每次 move 操作将会选择任意一个满足 0 的下标 i ，并将 nums[i] 递增 1 。返回使 nums 中的每个值都变成唯一的所需要的最少操作次数。生成的测试用例保证答案在 32 位整数范围内。示例 1：输入： nums = [1,2,2] 输出： 1 …

数组贪心排序计数

题目描述

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

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

生成的测试用例保证答案在 32 位整数范围内。

示例 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⁵

lightbulb

解题思路

方法一：排序 + 贪心

我们首先对数组 $\textit{nums}$ 进行排序，用一个变量 $\textit{y}$ 记录当前的最大值，初始时 $\textit{y} = -1$ 。

然后遍历数组 $\textit{nums}$ ，对于每个元素 $x$ ，我们将 $y$ 更新为 $\max(y + 1, x)$ ，并将操作次数 $y - x$ 累加到结果中。

遍历完成后，返回结果即可。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 是数组 $\textit{nums}$ 的长度。

1

2

3

4

5

6

7

8

9

class Solution:
    def minIncrementForUnique(self, nums: List[int]) -> int:
        nums.sort()
        ans, y = 0, -1
        for x in nums:
            y = max(y + 1, x)
            ans += y - x
        return ans

speed

复杂度分析

指标	值
时间	O(n+max)
空间	O(n+max)

psychology

面试官常问的追问

外企场景

question_mark
Assess the candidate's understanding of greedy algorithms and sorting strategies.
question_mark
Test if the candidate can efficiently track uniqueness in large arrays.
question_mark
Evaluate the candidate’s ability to implement efficient validation methods with minimal operations.

warning

常见陷阱

外企场景

error
Not sorting the array before applying the greedy strategy.
error
Failing to validate uniqueness efficiently, leading to redundant checks or incorrect results.
error
Incorrectly handling edge cases, such as when no increments are needed or when the array has duplicate values at the start.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if you needed to make the array unique by using both increments and decrements? How would the solution change?
arrow_right_alt
If the array could contain negative numbers, how would you modify the approach to ensure uniqueness?
arrow_right_alt
How would you approach this problem if you had to minimize both the number of moves and the final array sum?

help

常见问题

外企场景

继续练习

#1054 距离相等的条形码 #1090 受标签影响的最大值 #621 任务调度器