首页 > 代码库 > 【LeetCode】Longest Consecutive Sequence

【LeetCode】Longest Consecutive Sequence

2024-07-02 14:58:27   225人阅读

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.

 

想法一：

用01数组代表该数字是否存在序列中，化归为：一个01序列中，最长连续1的问题。

小数据上可以，但是大数据测试上遇到了问题，当数据跨度很大，比如INT_MIN~INT_MAX时，空间复杂度太高。

 

想法二：

用map代替数组实现上面的想法，可以解决空间复杂度问题。

但是在计算最长连续1的过程中发现新的问题，遍历INT_MIN~INT_MAX的时间复杂度太高。

 

参考了Discussion中的一些讨论，

想法三：

对1的元素进行左右最大扩展计数，访问过的元素置0防止计数冗余，代替全范围的遍历计数。

class Solution {
public:
    int longestConsecutive(vector<int> &num) 
    {
        map<int, bool> tag;
        for(vector<int>::size_type i = 0; i < num.size(); i ++)
        {// true 代表未访问过
            tag[num[i]] = true;
        }

        int count = 0;
        
        for(vector<int>::size_type i = 0; i < num.size(); i ++)
        {
            int curcount = 0;
            
            if(tag.find(num[i]) != tag.end() && tag[num[i]] == true)
            {
                tag[num[i]] = false;

                curcount ++;

                int left = num[i]-1;
                while(tag.find(left) != tag.end() && tag[left] == true)
                {
                    tag[left] = false;
                    curcount ++;
                    left -= 1;
                }

                int right = num[i]+1;
                while(tag.find(right) != tag.end() && tag[right] == true)
                {
                    tag[right] = false;
                    curcount ++;
                    right += 1;
                }

                if(curcount > count)
                    count = curcount;
            }
        }
        return count;
    }
};


联系
我们