题目

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.

分析

给定一个整形数组，求出最长的连续序列。例如数组[100,4,200,1,3,2]，最长的连续序列长度为[1,2,3,4]，长度为4。要求时间复杂度为O(n)。

首先，想到的办法就是 排序—>得到最长连续长度；但是不符合要求的时间复杂度，所以不予采用。

其次，第二个方法是利用c++中的set，直接会排序，并且没有重合的，但是set背后实现的原理牵扯到红黑树，时间复杂度同样不满足。

所以，解决该问题还是应该从哈希入手，建立hash索引，把查找的元素周围的都访问个遍，求出个临时最大值跟全局最大值比较。当再次访问该段的元素的时候，直接跳过。这样保证时间复杂度为O(n)。

c++11中数据结构为unordered_set，保证查找元素的时间复杂度为O(1)，但是奇怪的是我才用的unordered_set并没有通过，给出的结果是TLE，于是，我就改用了unordered_map最后通过测试。

AC代码

class Solution {

public:

    //方法一：使用unordered_set

    int longestConsecutive1(vector<int>& nums) {

        if (nums.empty() || nums.size() == 1)

            return nums.size();

        //保存序列元素个数

        int size = nums.size();

        unordered_set<int> existNums, visitedNums;

        for (int i = 0; i < size; ++i)

        {

            existNums.insert(nums[i]);

        }

        int maxCount = 0;

        for (int i = 0; i < size; ++i)

        {

            //每个连续序列中的元素只需要遍历一次,只有不在已遍历序列中时,向两侧探查

            if (visitedNums.find(nums[i]) != visitedNums.end())

                continue;

            int count = 1, less = nums[i] - 1, great = nums[i] + 1;

            while (existNums.find(less) != existNums.end())

            {

                visitedNums.insert(less);

                ++count;

                --less;

            }//while

            while (existNums.find(great) != existNums.end())

            {

                visitedNums.insert(great);

                ++count;

                --less;

            }//while

            if (count > maxCount)

                maxCount = count;

        }//for

        return maxCount;

    }

    //方法二：使用unordered_map

    int longestConsecutive(vector<int>& nums) {

        if (nums.empty() || nums.size() == 1)

            return nums.size();

        //保存序列元素个数

        int size = nums.size();

        unordered_map<int, bool> visitedNums;

        for (int i = 0; i < size; ++i)

        {

            visitedNums[nums[i]] = false;

        }

        int maxCount = 0;

        for (int i = 0; i < size; ++i)

        {

            //若已访问过，则跳过

            if (visitedNums[nums[i]])

                continue;

            int count = 1;

            //改变访问标记

            visitedNums[nums[i]] = true;

            int less = nums[i] - 1, great = nums[i] + 1;

            while (visitedNums.find(less) != visitedNums.end())

            {

                visitedNums[less] = true;

                --less;

                ++count;

            }//while

            while (visitedNums.find(great) != visitedNums.end())

            {

                visitedNums[great] = true;

                ++great;

                ++count;

            }//while

        if (count > maxCount)

                maxCount = count;

        }//for

        return maxCount;

    }

};

GitHub测试程序源码