128. longest continuous sequence hash table

128. The longest continuous sequence

Given an array of unsorted integers nums , Find the longest sequence of consecutive numbers （ Sequence elements are not required to be contiguous in the original array ） The length of .

Please design and implement it with a time complexity of O(n) The algorithm to solve this problem .

Example 1：

Input ：nums = [100,4,200,1,3,2]
Output ：4
explain ： The longest consecutive sequence of numbers is [1, 2, 3, 4]. Its length is 4.

Example 2：

Input ：nums = [0,3,7,2,5,8,4,6,0,1]
Output ：9

This question is actually problematic , Even a practical hash table cannot achieve o（1） The requirements of , There are certain problems in the title ：

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++)            // Traversing the array for the first time ———— Put the values of the array into the hash table ( Remove the weight at the same time )
    {
    
        struct MyNode* findNode=Find(nums[i],HashForNums);
        if(findNode==NULL) Insert(nums[i],HashForNums);
    }
    for(int i=0;i<numsSize;i++)   // Traverse the array for the second time ———— Find the length of a long continuous sequence 
    {
    
        if(nums[i]==-2147483647 || Find(nums[i]-1,HashForNums)==NULL)   // Only x-1 Look back when it doesn't exist ( Be careful ： The former comparison condition is to ensure that the type is int Of nums[i] Do not cross the boundary after subtracting one )
        {
    
            int curMax=0,temp=0;
            while(Find(nums[i]+temp,HashForNums)!=NULL)
            {
    
                curMax++;
                temp++;
            }
            max=fmax(curMax,max);
        }
    }
    return max;
}