[Leetcode] Longest Consecutive Sequence

偏执的太偏执、 2021-12-03 07:29 205阅读 0赞

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,  
Given `[100, 4, 200, 1, 3, 2]`,  
The longest consecutive elements sequence is `[1, 2, 3, 4]`. Return its length: `4`.

Your algorithm should run in O(*n*) complexity.

使用容器实现。已经判断过的不用再次判断。

1 class Solution {
     2 public:
     3     int longestConsecutive(vector<int> &num) {
     4         map<int, int> mp;
     5         for (int i = 0; i < num.size(); ++i) {
     6             mp[num[i]] = 1;
     7         }
     8         int len = 0, tmp;
     9         for (int i = 0; i < num.size(); ++i) {
    10             tmp = 1;
    11             if (mp[num[i]] == 1) {
    12                 int left = num[i] - 1;
    13                 while (mp.count(left) && mp[left] == 1) {
    14                     mp[left--] = 0;
    15                     ++tmp;
    16                 }
    17                 int right = num[i] + 1;
    18                 while (mp.count(right) && mp[right] == 1) {
    19                     mp[right++] = 0;
    20                     ++tmp;
    21                 }
    22                 len = (len > tmp) ? len : tmp;
    23             }
    24         }
    25         return len;
    26     }
    27 };

转载于:https://www.cnblogs.com/easonliu/p/3699679.html

发表评论取消回复

表情：

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

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

相关阅读

相关 leetcode 128. Longest Consecutive Sequence | 128. 最长连续序列（Java）

题目 [https://leetcode.com/problems/longest-consecutive-sequence/][https_leetcode.com_p

谁践踏了优雅/ 2023年01月23日 14:54/ 0 赞/ 121 阅读

相关 Longest Consecutive Sequence（C++最长连续序列）

（1）hash+优化 class Solution { public: int longestConsecutive(vector<in

Love The Way You Lie/ 2022年10月18日 12:56/ 0 赞/ 121 阅读

相关 leetcode 180. Consecutive Numbers

180. Consecutive Numbers Question Editorial Solution [My Submissions][] Total Ac

悠悠/ 2022年07月19日 01:54/ 0 赞/ 172 阅读

相关 leetcode 128. Longest Consecutive Sequence 最长连续序列 + HashSet查找的方法

Given an unsorted array of integers, find the length of the longest consecutive elements

清疚/ 2022年06月08日 05:36/ 0 赞/ 120 阅读

相关 [Leetcode][python]Longest Consecutive Sequence/最长连续序列

题目大意给定一组无序的整数，找出其中连续整数的最长长度。注意点：算法时间复杂度为O(n) 解题思路哈希表，遍历每个数，从中间扩展左右两边，不断刷新

迈不过友情╰/ 2022年06月05日 01:35/ 0 赞/ 182 阅读

相关 LeetCode-128：Longest Consecutive Sequence

题目 ![70][] 给出一个未排序的数组，找出最长的连续序列，连续指的是像……11、12、13、14……这样的，要求算法时间复杂度为O(n)。做一些说明

小鱼儿/ 2022年05月16日 13:21/ 0 赞/ 97 阅读

相关 LeetCode 128.Longest Consecutive Sequence (最长连续序列)

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

叁歲伎倆/ 2022年05月08日 06:04/ 0 赞/ 217 阅读

相关 LeetCode：128. Longest Consecutive Sequence（找出最大的连续子串）

> 文章最前：我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如

Dear 丶/ 2022年04月04日 03:26/ 0 赞/ 174 阅读

相关 leetcode128. Longest Consecutive Sequence 最长连续序列并查集

题目地址：[https://leetcode.com/problems/longest-consecutive-sequence/][https_leetcode.com_pr

柔光的暖阳◎/ 2022年03月31日 08:43/ 0 赞/ 200 阅读

相关 [Leetcode] Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements

偏执的太偏执、/ 2021年12月03日 07:29/ 0 赞/ 206 阅读