首页 > 代码库 > Longest Consecutive Sequence

Longest Consecutive Sequence

2024-07-17 10:48:04   225人阅读

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.

思路：由于题目要求O(n)的时间复杂度，如果序列是有序的，显然很容易满足要求。但是一般的排序算法的时间度为O(nlogn)，因此不能通过排序来解该题。

        题目要求求解最长的连续序列，而对于整数num，我们可以通过使用基于hash函数的map或者set以O(1)的复杂度确定num-1和num+1是否存在于序列中。基于这种思想，通过一次遍历输入序列，不断地合并相邻的连续区间，从而求得最大连续区间的长度。

 1 class Solution { 2 public: 3     int longestConsecutive( vector<int> &num ) { 4         if( num.empty() ) { return 0; } 5         unordered_map<int,pair<int,int>> numArea; 6         int max_len = 1; 7         for( size_t i = 0; i != num.size(); ++i ) { 8             // 若num[i]已经出现过，continue。 9             if( numArea.find( num[i] ) != numArea.end() ) { continue; }10             // 查找num[i]-1和num[i]+1。11             auto down = numArea.find( num[i]-1 ), up = numArea.find( num[i]+1 );12             if( down != numArea.end() && up != numArea.end() ) {13                 // num[i]-1和num[i]+1都存在。14                 if( down->second.first >= 1  ) { down = numArea.find( num[i]-1-down->second.first ); }15                 if( up->second.second >= 1 ) { up = numArea.find( num[i]+1+up->second.second ); }16                 down->second.second += up->second.first + 2;17                 up->second.first = down->second.second;18                 if( max_len < up->second.first + 1 ) { max_len = up->second.first + 1; }19                 numArea[num[i]] = make_pair( 0, 0 );20             } else if( down != numArea.end() ){21                 // num[i]-1存在。22                 if( down->second.first >= 1  ) { down = numArea.find( num[i]-1-down->second.first ); }23                 ++down->second.second;24                 if( max_len < down->second.second + 1 ) { max_len = down->second.second + 1; }25                 numArea[num[i]] = make_pair( down->second.second, 0 );26             } else if( up != numArea.end() ){27                 // num[i]+1存在。28                 if( up->second.second >= 1 ) { up = numArea.find( num[i]+1+up->second.second ); }29                 ++up->second.first;30                 if( max_len < up->second.first + 1 ) { max_len = up->second.first + 1; }31                 numArea[num[i]] = make_pair( 0, up->second.first );32             } else {33                 // num[i]-1和num[i]+1都不存在。34                 numArea[num[i]] = make_pair( 0, 0 );35             }36         }37         return max_len;38     }39 };

上述方法实现起来较为复杂，一种更加简洁直观的方法是：将序列存入set，然后每次删除一段连续区间，并统计该区间的长度，从而求得最大连续区间的长度。

 1 class Solution { 2 public: 3     int longestConsecutive(vector<int> &num) { 4         if( num.size() <= 1 ) { return num.size(); } 5         unordered_set<int> numSet; 6         // insert all elements to numSet. 7         for( size_t i = 0; i != num.size(); ++i ) { 8             if( numSet.find( num[i] ) == numSet.end() ) { 9                 numSet.insert( num[i] );10             }11         }12         // find longest consecutive sequence.13         int len = 1;14         while( !numSet.empty() ) {15             int aNum = *(numSet.begin()); numSet.erase( aNum );16             int cnt = 1, tmp = aNum;17             while( numSet.find( --tmp ) != numSet.end() ) { numSet.erase( tmp ); ++cnt; }18             tmp = aNum;19             while( numSet.find( ++tmp ) != numSet.end() ) { numSet.erase( tmp ); ++cnt; }20             if( cnt > len ) { len = cnt; }21         }22         return len;23     }24 };

 


联系
我们