Description
You are given an integer array nums. In one move, you can pick an index i where 0 <= i < nums.length and increment nums[i] by 1.
Return the minimum number of moves to make every value in nums unique.
The test cases are generated so that the answer fits in a 32-bit integer.
Example 1:
Input: nums = [1,2,2] Output: 1 Explanation: After 1 move, the array could be [1, 2, 3].
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 that it is impossible for the array to have all unique values with 5 or less moves.
Constraints:
1 <= nums.length <= 1050 <= nums[i] <= 105
Solutions
Solution 1: Sorting + Greedy
First, we sort the array nums, and use a variable y to record the current maximum value, initially y = -1.
Then, we iterate through the array nums. For each element x, we update y to max(y + 1, x), and accumulate the operation count y - x into the result.
After completing the iteration, we return the result.
The time complexity is O(n log n), and the space complexity is O(log n). Here, n is the length of the array nums.
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(code-box)
Solution 2: Counting + Greedy
According to the problem description, the maximum value of the result array m = max(nums) + len(nums). We can use a counting array cnt to record the occurrence count of each element.
Then, we iterate from 0 to m - 1. For each element i, if its occurrence count cnt[i] is greater than 1, then we add cnt[i] - 1 elements to i + 1, and accumulate the operation count into the result.
After completing the iteration, we return the result.
The time complexity is O(m), and the space complexity is O(m). Here, m is the length of the array nums plus the maximum value in the array.
Python3
class Solution:
def minIncrementForUnique(self, nums: List[int]) -> int:
m = max(nums) + len(nums)
cnt = Counter(nums)
ans = 0
for i in range(m - 1):
if (diff := cnt[i] - 1) > 0:
cnt[i + 1] += diff
ans += diff
return ans
Java
class Solution {
public int minIncrementForUnique(int[] nums) {
int m = Arrays.stream(nums).max().getAsInt() + nums.length;
int[] cnt = new int[m];
for (int x : nums) {
++cnt[x];
}
int ans = 0;
for (int i = 0; i < m - 1; ++i) {
int diff = cnt[i] - 1;
if (diff > 0) {
cnt[i + 1] += diff;
ans += diff;
}
}
return ans;
}
}
C++
class Solution {
public:
int minIncrementForUnique(vector<int>& nums) {
int m = *max_element(nums.begin(), nums.end()) + nums.size();
int cnt[m];
memset(cnt, 0, sizeof(cnt));
for (int x : nums) {
++cnt[x];
}
int ans = 0;
for (int i = 0; i < m - 1; ++i) {
int diff = cnt[i] - 1;
if (diff > 0) {
cnt[i + 1] += diff;
ans += diff;
}
}
return ans;
}
};
Go
func minIncrementForUnique(nums []int) (ans int) {
m := slices.Max(nums) + len(nums)
cnt := make([]int, m)
for _, x := range nums {
cnt[x]++
}
for i := 0; i < m-1; i++ {
if diff := cnt[i] - 1; diff > 0 {
cnt[i+1] += diff
ans += diff
}
}
return ans
}
TypeScript
function minIncrementForUnique(nums: number[]): number {
const m = Math.max(...nums) + nums.length;
const cnt: number[] = Array(m).fill(0);
for (const x of nums) {
cnt[x]++;
}
let ans = 0;
for (let i = 0; i < m - 1; ++i) {
const diff = cnt[i] - 1;
if (diff > 0) {
cnt[i + 1] += diff;
ans += diff;
}
}
return ans;
}
