Leetcode——945. 使数组唯一的最小增量

三种方法：提供c++实现，具体思路可看
leetcode题解

class Solution
{
public:
    int minIncrementForUnique(vector<int>& A)
    {
        int length=A.size();
        int re=0;
        sort(A.begin(),A.end());
        unordered_set<int> s;
        for(int i=1;i<length;i++)
        {
            if(A[i]<=A[i-1])
            {
                re=re+A[i-1]+1-A[i];
                A[i]=A[i-1]+1;
            }
        }
        return re;
    }
};

class Solution
{
public:
    int minIncrementForUnique(vector<int>& A)
    {
        int index[40002]={0};
        for(int i=0;i<A.size();i++)
        {
            index[A[i]]++;
        }
        int re=0;
        for(int i=0;i<40001;i++)
        {
            if(index[i]>1)
            {
                int temp=index[i]-1;
                re+=temp;
                index[i+1]+=(index[i]-1);
            }
        }
        int temp=index[40001];
        if(temp>0)
        {
            re=re+(temp-1)*temp/2;
        }
        return re;
    }
};

class Solution
{
public:
    int index[80001]={0};
    int findnext(int a)
    {
        int x=index[a];
        if(x==0)
        {
            index[a]=a+1;
            return a;
        }
        else
        {
            x=findnext(x);
            index[a]=x+1;
            return x;
        }
    }
    int minIncrementForUnique(vector<int>& A)
    {
        int re=0;
        for(int i=0;i<A.size();i++)
        {
            re+=findnext(A[i])-A[i];
        }
        return re;
    }
};

实现方法2  循环代替递归

class Solution
{
public:
    int minIncrementForUnique(vector<int>& A)
    {
        int index[80001]={0};
        int re=0;
        int road;
        for(int i=0;i<A.size();i++)
        {
            int temp=A[i];
            if(index[temp]==0)
            {
                index[temp]=temp+1;
            }
            else
            {
                road=index[temp];
                int end=road;
                while(index[end]!=0)
                {
                    end=index[end];
                }
                re=re+end-temp;
                while(index[road]!=0)
                {
                    int temp1=road;
                    road=index[road];
                    index[temp1]=end+1;
                }
                index[end]=end+1;
            }
        }
        return re;
    }
};