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) { int n = nums.size(), maxi = 0, cnt, i, k; if(n <= 0) return 0; unordered_set<int> numsSet; for(i = 0; i < n; i++) { numsSet.insert(nums[i]); } for(i = 0; i < n; i++) { cnt = 1; numsSet.erase(nums[i]); for(k = nums[i]+1; numsSet.find(k) != numsSet.end(); k++) { cnt++; numsSet.erase(k); } for(k = nums[i]-1; numsSet.find(k) != numsSet.end(); k--) { cnt++; numsSet.erase(k); } if(cnt > maxi) maxi = cnt; } return maxi; } };
先遍历数组，把所有元素放到一个set中。
然后再遍历数组，对每个元素，在set中找比它大的连续数字和比它小的连续数字，若找到则计数器加一，同时从set中删除这个数字。
128. Longest Consecutive Sequence *HARD* -- 寻找无序数组中最长连续序列的长度
原文：http://www.cnblogs.com/argenbarbie/p/5469869.html