leetcode做题笔记128. 最长连续序列-Toy模板网

这篇具有很好参考价值的文章主要介绍了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;
}