Longest Consecutive Sequence解题报告

Description:

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
Your algorithm should run in O(n) complexity.

Example:

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Link:

https://leetcode.com/problems/longest-consecutive-sequence/description/

解题方法：

这道题要求在O(n)时间解出，所以不能对数组进行排序。
解题思路参考：https://blog.csdn.net/fightforyourdream/article/details/15024861
O(n)解法为：把所有数都存到hashset中去，每遇到一个数，就把比它大的和比它小的连续的数都找一遍，在找的过程中把这些数都从hashset中删掉，防止重复查找。
比如例子：100, 4, 200, 1, 3, 2都加入hashset
当找100时，把100删掉，此时hashset: 4, 200, 1, 3, 2
.
.
.
当找到4时，找完以后的hashset: 200 （100在第一轮被删掉，1 2 3都在找比4小的连续数过程中都被删掉）

Time Complexity：

O(N)

完整代码：

int longestConsecutive(vector<int>& nums) {
    unordered_set<int> hash;
    for(int i: nums)
        hash.insert(i);
    int result = 0;
    for(int i: nums) {
        int cnt = 1;
        hash.erase(i);
        int temp = i - 1;
        //find less
        while(hash.find(temp) != hash.end()) {
            cnt++;
            hash.erase(temp--);
        }
        temp = i + 1;
        while(hash.find(temp) != hash.end()) {
            cnt++;
            hash.erase(temp++);
        }
        result = max(result, cnt);
    }
    return result;
}