LeetCode实战128 最长连续序列

原题链接

题目描述

给定一个未排序的整数数组，找出最长连续序列的长度。

要求算法的时间复杂度为。

示例:

输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

题目解析

乍一看，我们能马上想到的方法，就是先进行一次排序，再查找，可是就算我们常用的快速排序也有的复杂度，不合题意，所以这道题我们不能直接用排序。

这时，我们可以牺牲一些空间，来降低时间复杂度。

解法：哈希表

将无序变为有序，并不一定需要直接排序，我们可以用哈希表来“曲线救国”。虽然题目给出的序列是无序的，但是哈希表可以非常高效地访问无序序列。

我们可以建立一个无序哈希表unordered_map<int, bool> visited,哈希表的键对应数组的索引，其值表示数组中的元素是否被访问过。

对于每个元素，我们可以以该元素为中心，分别向左、向右查找连续元素，直到不连续为止，记录这个序列的长度，直到找出最大长度。

遍历每个元素，再以每个元素为中心再次进行迭代，似乎，这是一个的算法呀？

别担心！在遍历每个中心元素时，我们会把标记为true的元素跳过，因为，在这个题目的条件下，一个元素只能属于一个连续序列 ，所以我们无需再关心被访问过的中心元素，它一定会被某一个连续序列所包含。我们的算法，仍然属于级别。

代码：

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_map<int, bool> visited;
        for(auto i : nums)
            visited[i] = false;
        int maxLen = 0;
        
        for(auto i : nums){
            if(visited[i])continue;//如果这个元素被访问过，那么他一定就不再属于另外一个连续序列，直接跳过
            
            int len = 1;//当前序列的长度
            visited[i] = true;
            for(int j = i + 1; visited.find(j) != visited.end(); ++j){
                visited[j] = true;
                len++;
            }
            for(int j = i - 1; visited.find(j) != visited.end(); --j){
                visited[j] = true;
                len++;
            }
            maxLen = max(maxLen, len);
        }
        return maxLen;
    }
};

复杂度分析

时间复杂度：，请仔细思考上面的解题思路

空间复杂度：，因为引入了一个哈希表