[LeetCode]Longest Consecutive Sequence

简介:

题目大意

给定一个整形数组,求出最长的连续序列。例如数组[100,4,200,1,3,2],最长的连续序列长度为[1,2,3,4],长度为4。要求时间复杂度为O(n)。

 

思路

  1. "排序转换成经典的动态规划问题"的话排序至少需要时间复杂度为O(nlog(n))——pass
  2. 利用c++中的set,直接会排序,并且没有重合的,但是set背后实现的原理牵扯到红黑树,时间复杂度不满足——pass
  3. 建立hash索引,把查找的元素周围的都访问个遍,求出个临时最大值跟全局最大值比较。当再次访问该段的元素的时候,直接跳过。这样保证时间复杂度为O(n),c++11中数据结构为unordered_set,保证查找元素的时间复杂度为O(1).

伪代码

复制代码
建立无序集合existSet visitedSet分别表示原集合中包含的元素和已经访问了的元素
全局最大个数maxLen
顺序遍历原集合中的元素
    临时计数count=1
    如果该元素在visitedSet,停止往下执行,进行下一次循环
    否则,把改元素小的并且在existSet中的元素存放在visitedSet中,count++
         把改元素大的并且在existSet中的元素存放在visitedSet中, count++
    maxLen = max(maxLen, count)
复制代码

 

参考代码

复制代码
class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        if(num.empty())
            return 0;
        unordered_set<int> existSet;
        unordered_set<int> visitedSet;
        int maxLen;
        for(int i = 0; i < num.size(); ++i)
            existSet.insert(num[i]);
        for(int i = 0; i < num.size(); ++i)
        {
            if(visitedSet.find(num[i]) != visitedSet.end())
                continue;
            int count = 1;
            int left = num[i];
            while(existSet.find(--left) != existSet.end())
            {
                ++count;
                visitedSet.insert(left);
            }
            int right = num[i];
            while(existSet.find(++right) != existSet.end())
            {
                ++count;
                visitedSet.insert(right);
            }
            maxLen = maxLen > count ? maxLen : count;
        }
        return maxLen;
    }
};
复制代码

 





本文转自jihite博客园博客,原文链接:http://www.cnblogs.com/kaituorensheng/p/3675632.html,如需转载请自行联系原作者

相关文章
Leetcode 516. Longest Palindromic Subsequence
找到一个字符串的最长回文子序列,这里注意回文子串和回文序列的区别。子序列不要求连续,子串(substring)是要求连续的。leetcode 5. Longest Palindromic Substring就是求连续子串的。
49 0
|
Java
Leetcode 3. Longest Substring Without Repeating Characters
此题题意是找出一个不包含相同字母的最长子串,题目给出了两个例子来说明题意,但这两个例子具有误导性,让你误以为字符串中只有小写字母。还好我是心机boy,我把大写字母的情况也给考虑进去了,不过。。。。字符串里竟然有特殊字符,于是贡献了一次wrong answer,这次我把ascii字符表都考虑进去,然后就没问题了。这个故事告诫我们在编程处理问题的时候一定要注意输入数据的范围,面试中可以和面试官去确认数据范围,也能显得你比较严谨。
50 3
LeetCode 424. Longest Repeating Character Replacem
给你一个仅由大写英文字母组成的字符串,你可以将任意位置上的字符替换成另外的字符,总共可最多替换 k 次。在执行上述操作后,找到包含重复字母的最长子串的长度。
104 0
LeetCode 424. Longest Repeating Character Replacem
LeetCode 409. Longest Palindrome
给定一个包含大写字母和小写字母的字符串,找到通过这些字母构造成的最长的回文串。 在构造过程中,请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。
74 0
LeetCode 409. Longest Palindrome
LeetCode 395. Longest Substring with At Least K
找到给定字符串(由小写字符组成)中的最长子串 T , 要求 T 中的每一字符出现次数都不少于 k 。输出 T 的长度。
91 0
LeetCode 395. Longest Substring with At Least K
|
Windows
LeetCode 388. Longest Absolute File Path
我们致力于寻找我们文件系统中文件的最长 (按字符的数量统计) 绝对路径。例如,在上述的第二个例子中,最长路径为 "dir/subdir2/subsubdir2/file2.ext",其长度为 32 (不包含双引号)。
84 0
LeetCode 388. Longest Absolute File Path
|
存储
LeetCode 329. Longest Increasing Path in a Matrix
给定一个整数矩阵,找出最长递增路径的长度。 对于每个单元格,你可以往上,下,左,右四个方向移动。 你不能在对角线方向上移动或移动到边界外(即不允许环绕)。
71 0
LeetCode 329. Longest Increasing Path in a Matrix
|
算法
LeetCode 300. Longest Increasing Subsequence
给定一个无序的整数数组,找到其中最长上升子序列的长度。
54 0
LeetCode 300. Longest Increasing Subsequence
|
算法
LeetCode 128. Longest Consecutive Sequence
给定一个未排序的整数数组,找出最长连续序列的长度。 要求算法的时间复杂度为 O(n)。
88 0
LeetCode 128. Longest Consecutive Sequence
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行