---
# System prepended metadata

title: Minimum Increment to Make Array Unique
tags: [Array, LeetCode]

---

---
description: Today 1 leet , tomorrow 頂天leet地
image: https://leetcode.com/static/images/LeetCode_Sharing.png
---
# Minimum Increment to Make Array Unique
[題目網址<i class="fa fa-link"></i>](https://leetcode.com/problems/minimum-increment-to-make-array-unique/)
## 題目敘述
Given an array of integers nums, a move consists of choosing any `nums[i]`, and incrementing it by `1`.

Return the least number of moves to make every value in `nums` unique.
:::spoiler **Example 1**

> **Input:** [1,2,2]
> **Output:** 1
> **Explanation:**  After 1 move, the array could be [1, 2, 3].
:::

:::spoiler **Example 2**
> **Input:** nums = [3,2,1,2,1,7]
> **Output:** 6
> **Explanation:** After 6 moves, the array could be [3, 4, 1, 2, 5, 7].
It can be shown with 5 or less moves that it is impossible for the array to have all unique values.
:::


## 解題思維
將nums排序，預設pre=nums[0]，遍歷nums並計算pre-num[i]的總和
(檢測pre與num[i]大小關係👉找尋差值👉更新pre值)

## 程式碼

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



$O(N\log_2N)$



###### tags: `LeetCode` `Array`