题目大意
给定一个整形数组，求出最长的连续序列。例如数组[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; } };
本文转自jihite博客园博客，原文链接：http://www.cnblogs.com/kaituorensheng/p/3675632.html，如需转载请自行联系原作者
