128. Longest Consecutive Sequence

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.

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if(nums.size()<=0)
          return 0;
        unordered_set<int> exsitSet;
        unordered_set<int> visitedSet;
        for(int i=0;i<nums.size();i++)
          exsitSet.insert(nums[i]);
        int maxLen = 0;
        for(int i=0;i<nums.size();i++)
        {
            if(visitedSet.find(nums[i]) != visitedSet.end())
              continue;
            int count = 1;
            int left = nums[i];
            while(exsitSet.find(--left) != exsitSet.end())
            {
                count++;
                visitedSet.insert(left);
            }
            int right = nums[i];
            while(exsitSet.find(++right) != exsitSet.end())
            {
                count++;
                visitedSet.insert(right);
            }
            maxLen = max(maxLen,count);
        }
        return maxLen;
    }
};
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容