945.使数组唯一的最小增量 (Medium)*

class Solution {
public:
    enum { MAXN = 80001 };
    int mark[MAXN] = {0};
    int minIncrementForUnique(vector<int>& A) {
        if(A.size() <= 0){
            return 0;
        }
        int maxValue = 0;
        for(size_t i = 0, n = A.size(); i < n; ++i){
            ++mark[A[i]];
            maxValue = max(maxValue, A[i]);
        }
        int ans = 0;
        maxValue <<= 1;
        for(int i = 0; i <= maxValue; ++i){
            if(mark[i] > 1){
                ans += mark[i] - 1;
                mark[i+1] += mark[i]-1;
                mark[i] = 1;
            }
        }
        return ans;
    }
};

class Solution {
private:
    void quickSort(vector<int>& nums, int l, int r) {
        if(l >= r) {
            return;
        }
        swap(nums[l], nums[l + rand() % (r - l + 1)]);
        int finalPos = l + 1;
        for(int i = l + 1; i <= r; i++) {
            if(nums[i] < nums[l]) {
                swap(nums[finalPos++], nums[i]);
            }
        }
        swap(nums[--finalPos], nums[l]);
        quickSort(nums, l, finalPos - 1);
        quickSort(nums, finalPos + 1, r);
    }
public:
    int minIncrementForUnique(vector<int>& nums) {
        int len = nums.size();
        quickSort(nums, 0, len - 1);
        int res = 0;
        for(int i = 1; i < len; i++) {
            int diff = nums[i - 1] - nums[i] + 1;
            if(diff > 0) {
                res += diff;
                nums[i] += diff;
            }
        }
        return res;
    }
};