专栏首页算法码上来每日算法系列【LeetCode 128】最长连续序列

每日算法系列【LeetCode 128】最长连续序列

题目描述

给定一个未排序的整数数组,找出最长连续序列的长度。

要求算法的时间复杂度为 。

示例1

输入:
[100, 4, 200, 1, 3, 2]
输出:
4
解释:
最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

题解

哈希表

因为题目要求 的时间复杂度,所以不能排序。

我们可以遍历每个数 ,假设它是某个连续序列的开头,那么首先要满足 不在数组中,然后从 开始逐渐增大,看最大多少还在数组里。

实现上查询数字在不在数组里可以采用哈希表,复杂度是 的。虽然看起来遍历每个数是 ,以它为开头逐渐增大又是 ,但是我们其实只会对开头的数遍历最大能达到多少。这样两层循环总的遍历次数其实还是 的。

总的时间复杂度就是 。

并查集

我们可以把任意两个相差为 的数之间连上边,那么数组就变成了若干个子树,我们只需要求结点数量最多的那个子树就行了。

用并查集可以实现连接两个连续序列,合并成一个连续序列,并且快速查询这个序列长度是多少。

首先初始的时候,数组中的每个数都自成一个子树(它自己就是根结点)。然后遍历每一个数 ,如果 也在数组中,那就合并这两个数所在的子树,并且统计合并后的子树大小。

总的时间复杂度也是 。

代码

哈希表(c++)

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_map<int, int> mp;
        for (auto x : nums) mp[x] = 1;
        int res = 0;
        for (auto x : nums) {
            if (mp.count(x-1)) continue;
            int y = x;
            while (mp.count(++y));
            res = max(res, y-x);
        }
        return res;
    }
};

并查集(c++)

class Solution {
public:
    unordered_map<int, int> fa, cnt;

    int find(int x) {
        return x==fa[x] ? x : fa[x]=find(fa[x]);
    }

    int merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return cnt[x];
        fa[y] = x;
        cnt[x] += cnt[y];
        return cnt[x];
    }

    int longestConsecutive(vector<int>& nums) {
        if (!nums.size()) return 0;
        for (auto x : nums) {
            fa[x] = x;
            cnt[x] = 1;
        }
        int res = 1;
        for (auto x : nums) {
            if (fa.count(x+1)) {
                res = max(res, merge(x, x+1));
            }
        }
        return res;
    }
};

作者简介:godweiyang知乎同名华东师范大学计算机系硕士在读,方向自然语言处理与深度学习。喜欢与人分享技术与知识,期待与你的进一步交流~

本文分享自微信公众号 - 算法码上来(GodNLP),作者:godweiyang

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-03-03

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【每日算法Day 63】LeetCode 第 179 场周赛题解

    https://leetcode-cn.com/problems/generate-a-string-with-characters-that-have-odd...

    godweiyang
  • 【每日算法Day 94】经典面试题:机器人的运动范围

    地上有一个 m 行 n 列的方格,从坐标 [0, 0] 到坐标 [m-1, n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动,它每次可以向左、右、上、...

    godweiyang
  • 每日算法系列【EOJ 3031】二进制倒置

    给定一个整数 、将 的 334 位二进制表示形式(不包括开头可能的值为 0 的位, 表示为 1 位 0)前后倒置,输出倒置后的二进制数对应的整数。

    godweiyang
  • go语言的数组和切片区别

    可以得出结论:如官方文档所述,数组是需要指定个数的,而切片则不需要。数组赋值也可是使用如下方式,忽略元素个数,使用“...”代替

    charlieroro
  • 1073 多选题常见计分法 (20 分)

    可爱见见
  • C#生成随机验证码

    易墨
  • CSU1216: 异或最大值(01Trie树)

    多组数据。第一行为数字个数n,1 <= n <= 10 ^ 5。接下来n行每行一个32位有符号非负整数。

    attack
  • BZOJ3265: 志愿者招募加强版(线性规划)

    attack
  • 验证码类

    剑行者
  • 西南民族大学程序竞赛

    No matter what activities you join,whether you want or not, you could gain unexp...

    AngelNH

扫码关注云+社区

领取腾讯云代金券