首页 > 代码库 > 【leetcode】Longest Consecutive Sequence

【leetcode】Longest Consecutive Sequence

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.

 
 
利用一个hash表去存储这个数组,对于hash表中的元素,可以去查找比他大的相邻的元素,以及比他小相邻的元素,进而确定最长连续串。
 

以题目给出的数组为例:对于100,先向下查找99没找到,然后向上查找101也没找到,那么连续长度是1,从哈希表中删除100;然后是4,向下查找找到3,2,1,向上没有找到5,那么连续长度是4,从哈希表中删除4,3,2,1。这样对哈希表中已存在的某个元素向上和向下查找,直到哈希表为空。算法相当于遍历了一遍数组,然后再遍历了一遍哈希表,复杂的为O(n)

 
 
 1 class Solution { 2 public: 3     int longestConsecutive(vector<int> &num) { 4         5         unordered_set<int> hash; 6         unordered_set<int>::iterator it; 7         8         for(int i=0;i<num.size();i++) hash.insert(num[i]); 9        10         int count;11         int result=0;12         while(!hash.empty())13         {14             count=1;15            16             it=hash.begin();17             int num0=*it;18             hash.erase(num0);19            20             int num=num0+1;21             while(hash.find(num)!=hash.end())22             {23                 count++;24                 hash.erase(num);25                 num++;26             }27            28             num=num0-1;29             while(hash.find(num)!=hash.end())30             {31                 count++;32                 hash.erase(num);33                 num--;34             }35            36             if(result<count) result=count;37         }38        39         return result;40     }41 };

 

 

【leetcode】Longest Consecutive Sequence