leetcode---945. 使數組唯一的最小增量

方法一：暴力,對于數組中的每一個數使其遞增到數組裡不存在的數為止，每增一次計數加一。

int minIncrementForUnique(vector<int>& A) {
    int vis[90005]={0},cont = 0;
    for(int i = 0;i < A.size();i++)
    {
        vis[A[i]]++;
    }
    for(int i = 0;i < A.size();i++)
    {
        if(vis[A[i]] == 1)
            continue;
        int num = A[i];
        do{
            num++;
            cont++;
        }while(vis[num] != 0);
        vis[num] = 1;
        vis[A[i]]--;
    }
    return cont;
}
           

方法二：對每個數字進行計數，周遊計數數組，把出現1次以上的數放在a數組中，當周遊到空缺位置時，可在a數組中任選一個數字使其遞增到該數。該方法對方法一進行了優化，避免我們每次都要重新周遊找一個空缺位置。

int minIncrementForUnique(vector<int>& A) {
    int vis[80000]={0},a[40001];
    for(auto i:A) vis[i]++;
    int cont = 0,cnt = 0,j = 0;
    for(int i = 0;i < 80000;i++)
    {
        while(vis[i] > 1)
        {
            a[cnt++] = i;
            vis[i]--;
        }
        if(j < cnt && vis[i] == 0){
            cont += i-a[j++];
        }
    }
    return cont;
}
           

方法三：其實對于方法二我們并不需要一個額外的數組來存放重複的數字，我們可以設定一個變量來存放有總共由有多少個數字重複(用于确定我們需要多少個空位)，并且對于一個重複的數來說我們可以直接從操作數中減去    重複數字的個數*該數    (因為我們每找到一個數組中不存在的數時，我們需要将重複的數字遞增為該數，操做次數等于：數組中不存在的數-重複的數,若我們先将重複的數減去，當我們找到的一個  數組中不存在的數時，隻需使操作數加該數，這樣做的好處是我們不需要關心将哪個重複的數字遞增到我們所找到的  數組中不存在的數，我們隻用關心我們是否将所有重複的數字操作完)

int minIncrementForUnique(vector<int>& A) {
    int vis[80000]={0};
    for(auto i:A) vis[i]++;
    int cont = 0,cnt = 0;
    for(int i = 0;i < 80000;i++)
    {
        if(vis[i] > 1)
        {
            cnt += vis[i]-1;
            cont -= (vis[i]-1)*i;
        }
        else if(cnt > 0 && vis[i] == 0){
            cont += i;
            cnt--;
        }
    }
    return cont;
}
           

方法四：排序。題目要求數組裡的數字不能重複，那我們先将數組排序，再使其完全遞增。

int minIncrementForUnique(vector<int>& A) {
    if(A.empty())
        return 0;
    sort(A.begin(),A.end());
    int cont = 0;
    for(int i = 0;i < A.size()-1;i++)
    {
        if(A[i+1] <= A[i])
        {
            cont += (A[i]-A[i+1]+1);
            A[i+1] = A[i]+1;
        }
    }
    return cont;
}
           

方法五：可以将這道題看成給你一堆數，将他們存放在數組中，這就類似于解決hash沖突(使用線性探測法+路徑壓縮)，每一個數的操作次數為實際存放的位置減去本該存放的位置，貼出大佬題解連結----->膜拜大佬

int vis[80000];
int minIncrementForUnique(vector<int>& A) {
    int cont = 0;
    fill(vis,vis+80000,-1);
    for(auto i:A)
    {
        int b = find(i);
        cont += b-i;
    }
    return cont;
}
int find(int a)
{
    if(vis[a] == -1)
    {
        vis[a] = a;
        return a;
    }
    int b = find(vis[a]+1);
    vis[a] = b;
    return b;
}