128. Plus longue séquence continue - table de hachage

128. La plus longue séquence continue

Compte tenu d'un tableau entier non trié nums ,Trouvez la plus longue séquence continue de nombres（Il n'est pas nécessaire que les éléments de séquence soient continus dans le tableau original）Longueur.

Veuillez concevoir et mettre en œuvre la complexité temporelle O(n) Algorithme pour résoudre ce problème.

Exemple 1：

Entrée：nums = [100,4,200,1,3,2]
Produits：4
Explication：La séquence numérique continue la plus longue est [1, 2, 3, 4].Sa longueur est 4.

Exemple 2：

Entrée：nums = [0,3,7,2,5,8,4,6,0,1]
Produits：9

C'est un problème.,Même les tables de hachage utilitaires ne peuvent pas atteindreo（1）Exigences,Le problème est qu'il y a un problème：

struct MyNode{
    
    int data;
    struct MyNode* next;
};
struct HashTbl{
    
    int TableSize;
    struct MyNode** TheLists;
};
int NextPrime(int n)
{
    
    if(n%2==0) n++;
    for(;;n+=2)
    {
    
        for(int i=3;i<=sqrt(n);i++)
           if(n%i==0) goto out;
        return n;
        out:;
    }
}
int Hash(int key,int TableSize)
{
    
    int ret=abs(key)%TableSize;
    return ret;
}
struct HashTbl* InitializeHashTbl(int TableSize)
{
    
    struct HashTbl* H=(struct HashTbl*)malloc(sizeof(struct HashTbl));
    H->TableSize=NextPrime(TableSize);
    H->TheLists=malloc(sizeof(struct MyNode*)*H->TableSize);
    for(int i=0;i<H->TableSize;i++)
    {
    
        H->TheLists[i]=malloc(sizeof(struct MyNode));
        H->TheLists[i]->next=NULL;
        H->TheLists[i]->data=-1;
    }
    return H;
}
struct MyNode* Find(int key,struct HashTbl* H)
{
    
    struct MyNode* p,*l;
    l=H->TheLists[Hash(key,H->TableSize)];
    p=l->next;
    while(p!=NULL&&p->data!=key)
       p=p->next;
    return p;
}
void Insert(int key,struct HashTbl* H)
{
    
    struct MyNode* Pos,*l;
    Pos=Find(key,H);
    if(Pos==NULL)
    {
    
        struct MyNode* NewCell=(struct MyNode*)malloc(sizeof(struct MyNode));
        l=H->TheLists[Hash(key,H->TableSize)];
        NewCell->next=l->next;
        l->next=NewCell;
        NewCell->data=key;
    }
}
void FreeHashTbl(struct HashTbl* H)
{
    
    struct MyNode* temp,*deleteNode;
    for(int i=0;i<H->TableSize;i++)
    {
    
        temp=H->TheLists[i];
        while(temp!=NULL)
        {
    
            deleteNode=temp;
            temp=temp->next;
            free(deleteNode);
        }
    }
    free(H);
}
int longestConsecutive(int* nums, int numsSize){
    
    int max=0;
    struct HashTbl* HashForNums=InitializeHashTbl(numsSize);
    for(int i=0;i<numsSize;i++)            //Première traversée du tableau———— Mettre la valeur du tableau dans la table de hachage (Et en même temps, on se débarrasse du poids)
    {
    
        struct MyNode* findNode=Find(nums[i],HashForNums);
        if(findNode==NULL) Insert(nums[i],HashForNums);
    }
    for(int i=0;i<numsSize;i++)   // Deuxième traversée du tableau ———— Trouver une longue longueur de séquence continue 
    {
    
        if(nums[i]==-2147483647 || Find(nums[i]-1,HashForNums)==NULL)   //Seulementx-1 Regardez en arrière quand il n'existe pas (Attention!： La condition de comparaison précédente est de s'assurer que le type est intDenums[i] Ne pas franchir la ligne après moins un )
        {
    
            int curMax=0,temp=0;
            while(Find(nums[i]+temp,HashForNums)!=NULL)
            {
    
                curMax++;
                temp++;
            }
            max=fmax(curMax,max);
        }
    }
    return max;
}