[LeetCode]Longest Consecutive Sequence-阿里云开发者社区

[LeetCode]Longest Consecutive Sequence

2017-11-09 848

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介：

题目大意

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

思路

"排序转换成经典的动态规划问题"的话排序至少需要时间复杂度为O(nlog(n))——pass
利用c++中的set，直接会排序，并且没有重合的，但是set背后实现的原理牵扯到红黑树，时间复杂度不满足——pass
建立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;
    }
};