128. Longest Consecutive Sequence

problem 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:

Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

algorithm thought

这里要求需要使用O(n)时间求解，我们必须引入一个新的数据结果来使访问一个数据的时间控制到O(1)时间。那肯定是unordered_set类型，这个数据结构是基于hashmap实现的，插入和查询时间是O(1)。首先我们将所有数据存入set，然后顺序遍历原来的数组，如果数字的前一个在set中存在，continue，否则，表示这个数字是这段数字的开始，于是从这里开始顺序加一，每次结果在set中查询，知道不存在这个数字。最后求最长的解

code

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> s(nums.begin(),nums.end());
        int best=0;
        for(int val:nums)
        {
            if(s.count(val-1)) continue;
            int y=val+1;
            while(s.count(y))
            {
                y++;
            }
            best=max(best,y-val);            
        }
        return best;
    }
};

algorithm analysis

开始将vector数据复制到unordered_set中，时间复杂度O(n).注意一定要使用这种办法而不是一个个插入的方法，如果一个个插入很可能耗时更多。然后遍历数组时间复杂度O(n),在循环中会再次遍历一遍顺序的数字，这里需要执行n次。 最后执行3n次，时间复杂度O(n)