LeetCode128.最长连续序列每日一题6月6日

红太狼 2023-02-15 13:59 35阅读 0赞

## 问题描述： ##

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

要求算法的时间复杂度为 O(n)。

来源：力扣（LeetCode）  
链接：[https://leetcode-cn.com/problems/longest-consecutive-sequence][https_leetcode-cn.com_problems_longest-consecutive-sequence]

示例:

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

## 解题思路： ##

题意是时间复杂度为O(n)，那么我们肯定不能使用传统排序方法

那么只有使用空间换时间的方法，使用hash表一一映射

然后在查找是否有连续的

这里采用unordered\_set数据结构，unordered\_set的查找是基于哈希表的，并且具有去重复的功能

下面是完整代码：

class Solution {
    public:
        int longestConsecutive(vector<int>& nums) {
            unordered_set<int> se(nums.begin(),nums.end());
            int res =0;
            for(auto &x:se){
                if(!se.count(x-1)){
                    int cnt =1,num=x;
                    while(se.count(num+1)){cnt++;num++;}
                    res = max(res,cnt);
                }
            }
            return res;
        }
    };

[https_leetcode-cn.com_problems_longest-consecutive-sequence]: https://leetcode-cn.com/problems/longest-consecutive-sequence

发表评论取消回复

表情：

评论列表（有 0 条评论，35人围观）

还没有评论，来说两句吧...

相关阅读

相关（每日一练C++）128. 最长连续序列

前言 C++是一种计算机高级程序设计语言，由C语言扩展升级而产生，最早于1979年由本贾尼·斯特劳斯特卢普在AT&T贝尔工作室研发。 C++既可以进行C语言的过程化

怼烎@/ 2023年10月04日 18:30/ 0 赞/ 143 阅读

相关 128. 最长连续序列（高频题）

128. 最长连续序列解题思路代码解题思路 1. 对于数组nums，其可能有多个数字连续的序列，其中每个序列都会有一个左边界，例如示例1的结果

迈不过友情╰/ 2023年10月04日 08:43/ 0 赞/ 140 阅读

相关 LeetCode图解 | 128.最长连续序列

点击上方蓝字设为星标![format_png][] 下面开始今天的学习～ ![format_png 1][] 今天分享一个LeetCode题，题号是128，标题是最长连续

￡神魔★判官ぃ/ 2023年07月06日 14:51/ 0 赞/ 135 阅读

相关 leetcode128 最长连续序列

给定一个未排序的整数数组，找出最长连续序列的长度。要求算法的时间复杂度为 O(n)。示例: 输入: \[100, 4, 200, 1, 3, 2\] 输出: 4

分手后的思念是犯贱/ 2023年06月19日 09:46/ 0 赞/ 234 阅读

相关 Leetcode128. 最长连续序列

给定一个未排序的整数数组，找出最长连续序列的长度。要求算法的时间复杂度为 O(n)。 > 输入: \[100, 4, 200, 1, 3, 2\] > 输出: 4

绝地灬酷狼/ 2023年03月14日 08:06/ 0 赞/ 83 阅读

相关 LeetCode 128. 最长连续序列

这题考查对map的使用。最简单的思路应该是开一个数组，如果含有这个数就标记为1.但这样做有两个问题，第一数据太大，第二存在负值。因此只能使用map来记录。令map\[x

男娘i/ 2023年02月16日 12:26/ 0 赞/ 42 阅读

相关力扣LeetCode 128题：最长连续序列

题目： > 给定一个未排序的整数数组，找出最长连续序列的长度。 > 要求算法的时间复杂度为 O(n)。 > > 示例: > 输入: \[100, 4, 20

不念不忘少年蓝@/ 2023年02月16日 01:40/ 0 赞/ 35 阅读

相关 LeetCode128.最长连续序列每日一题6月6日

问题描述：给定一个未排序的整数数组，找出最长连续序列的长度。要求算法的时间复杂度为 O(n)。来源：力扣（LeetCode）链接：[https://lee

红太狼/ 2023年02月15日 13:59/ 0 赞/ 36 阅读

相关 Leetcode 128. 最长连续序列

题目重述给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

桃扇骨/ 2022年09月10日 00:29/ 0 赞/ 341 阅读

相关 LeetCode-128. 最长连续序列

[128. 最长连续序列][128.] 给定一个未排序的整数数组，找出最长连续序列的长度。要求算法的时间复杂度为 O(n)。示例: 输入: [100,

川长思鸟来/ 2022年02月20日 16:35/ 0 赞/ 338 阅读