leetcode做题笔记128. 最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

思路一：模拟题意（时间复杂度不合要求）

int cmp(const void* a,const void* b){
    return *(int*)a - *(int*)b;
}
int longestConsecutive(int* nums, int numsSize){
    if(numsSize == 0)
        return 0;
    qsort(nums,numsSize,sizeof(int),cmp);
    int max = 1,sum = 1;
    for(int i = 1;i < numsSize;i++){
        if(nums[i] == nums[i - 1] + 1)
            sum++;
        else if(nums[i] == nums[i - 1])
            continue;
        else
            sum = 1;
        max = max > sum ? max : sum;
    }
    return max;
}

思路二：哈希表

#define HASH_BASE  (10031)
 
int hash_index(int a)
{
    int t;
    
    t = a % HASH_BASE;
    if (t < 0) {
        t = HASH_BASE + t;
    }
    return t;
}
 
int longestConsecutive(int* nums, int numsSize){
    int i, cnt, lmax, cur;
    bool *hs;
 
    hs = malloc(sizeof(bool) * (HASH_BASE));
    memset(hs, 0, sizeof(bool) * (HASH_BASE));
 
    for (i = 0; i < numsSize; i++) {
        hs[hash_index(nums[i])] = true;
    }
 
    lmax = 0;
    for (i = 0; i < numsSize; i++) {
        if (!hs[hash_index(nums[i] - 1)]) {
            cnt = 1;
            cur = nums[i];
            while (hs[hash_index(cur + 1)]) {
                cnt++;
                cur++;
            }
            if (cnt > lmax) {
                lmax = cnt;
            }
        }
    }
    free(hs);
    return lmax;
}

分析：

本题要求最长连续序列，可以将先将数组内数先排序一遍，再向后不断遍历数组比较得到最长连续序列，但时间复杂度不合要求，可以想到若先将数组内数放置在哈希表中再查找时间复杂度仅为O(n)，所以将数存到哈希表中，利用find找到最长连续序列，最后输出即可

总结：

本题考察哈希表的应用，将值存入哈希表中再查找可达到O(n)的时间复杂度