Minimum Increment to Make Array Unique LT945

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

 

Idea 1. Once the array is sorted, the next available number is at least a big as the previous + 1, 

Time complexity: O(nlogn)

Space complexity: O(1), unless counting the space needed for sorting

class Solution {
    public int minIncrementForUnique(int[] A) {
        if(A.length == 0) {
            return 0;
        }
        
        Arrays.sort(A);
        int prev = A[0];
        int cnt = 0;
        for(int i = 1; i < A.length; ++i) {
            if(A[i] <= prev) {
                cnt += prev - A[i] + 1;
                prev += 1;
            }
            else {
                prev = A[i];
            }
        }
        return cnt;
    }
}

网上更简洁的方法，亮瞎眼啊

class Solution {
    public int minIncrementForUnique(int[] A) {
        if(A.length == 0) {
            return 0;
        }
        
        Arrays.sort(A);
        int nextAvailable = A[0] + 1;
        int cnt = 0;
        for(int i = 1; i < A.length; ++i) {
            cnt += Math.max(nextAvailable - A[i], 0);
            nextAvailable = Math.max(nextAvailable, A[i]) + 1;
        }
        return cnt;
    }
}

Idea 2. Map + count, didn't get the limit of 10000 at first, then imagin n= 4, instead of 10000, [4, 4, 4, 4], the max would be max(A) + len(A) -1 

Time complexity: O(n + max(A)), n = A.length

Space complexity: O(n + max(A))

class Solution {
    public int minIncrementForUnique(int[] A) {
        int n = A.length;
        int[] count = new int[80000];
        
        for(int a: A) {
            ++count[a];
        }
        
        int result = 0;
        int needed = 0;
        for(int i = 0; i < 80000; ++i) {
            if(count[i] >= 2) {
                 result -= (count[i]-1) * i; 
                 needed += count[i] - 1;
            }
            else if(needed > 0 && count[i] == 0) {
                --needed;
                result += i;
            }
        }
        
        return result;
    }
}