128. 最長連續序列-哈希錶

128. 最長連續序列

給定一個未排序的整數數組 nums ，找出數字連續的最長序列（不要求序列元素在原數組中連續）的長度。

請你設計並實現時間複雜度為 O(n) 的算法解决此問題。

示例 1：

輸入：nums = [100,4,200,1,3,2]
輸出：4
解釋：最長數字連續序列是 [1, 2, 3, 4]。它的長度為 4。

示例 2：

輸入：nums = [0,3,7,2,5,8,4,6,0,1]
輸出：9

這題其實是有問題的，即使實用哈希錶也不能達到o（1）的要求，題目是存在一定問題的：

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++)            //第一次遍曆數組————把數組的值放到哈希錶中(同時去重)
    {
    
        struct MyNode* findNode=Find(nums[i],HashForNums);
        if(findNode==NULL) Insert(nums[i],HashForNums);
    }
    for(int i=0;i<numsSize;i++)   //第二次遍曆數組————找長連續序列長度
    {
    
        if(nums[i]==-2147483647 || Find(nums[i]-1,HashForNums)==NULL)   //只有x-1不存在的時候再往後找(注意：前一項比較條件是確保類型為int的nums[i]在减一後不越界)
        {
    
            int curMax=0,temp=0;
            while(Find(nums[i]+temp,HashForNums)!=NULL)
            {
    
                curMax++;
                temp++;
            }
            max=fmax(curMax,max);
        }
    }
    return max;
}