# 945. Minimum Increment to Make Array Unique

Given an array of integers A, a  move  consists of choosing any `A[i]`, and incrementing it by `1`.

Return the least number of moves to make every value in `A` unique.

Example 1:

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

Example 2:

``````Input: [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.
``````

Note:

1. `0 <= A.length <= 40000`
2. `0 <= A[i] < 40000`

``````class Solution {
public:
int minIncrementForUnique(vector<int>& A) {
int res = 0, need = 0;
sort(A.begin(), A.end());
for (int num : A) {
res += max(need - num, 0);
need = max(num, need) + 1;
}
return res;
}
};
``````

``````class Solution {
public:
int minIncrementForUnique(vector<int>& A) {
int res = 0, need = 0;
map<int, int> numCnt;
for (int num : A) ++numCnt[num];
for (auto &a : numCnt) {
res += a.second * max(need - a.first, 0) + a.second * (a.second - 1) / 2;
need = max(need, a.first) + a.second;
}
return res;
}
};
``````

``````class Solution {
public:
int minIncrementForUnique(vector<int>& A) {
int res = 0;
unordered_map<int, int> root;
for (int num : A) {
res += find(root, num) - num;
}
return res;
}
int find(unordered_map<int, int>& root, int x) {
return root[x] = root.count(x) ? find(root, root[x] + 1) : x;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/945

https://leetcode.com/problems/minimum-increment-to-make-array-unique/

https://leetcode.com/problems/minimum-increment-to-make-array-unique/discuss/197687/JavaC%2B%2BPython-Straight-Forward

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation