最长连续序列 LeetCode(思维)

你的名字 2022-05-14 10:45 186阅读 0赞

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

要求算法的时间复杂度为 *O(n)*。

**示例:**

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

**题解:**

一开始开了个100w的数组，然后暴力扫，结果说输入的数据有-2^31和2^31这种变态数据，后来好好想了，然后tle了，优化了下最后a了，不过才击败了百分之20的人，或许是很久没写算法的原因了吧。该题目叙述不是很清楚，没有说重复的数据到底算不算，a了后才知道，其实是不算的。我的思路是用map记录数据，p\[i\]如果是一段序列的开头或者结尾，那么p\[i\]就是这段序列的长度，每一次插入只需要更新序列的首尾两个的值。

**具体:**

当扫到一个数字存在时，跳过。若不存在，假设该数字是i，初始化len=1，那么加上后面的长度:len+p\[i+1\]，那么最后一个元素的下标可以计算出是i+p\[i+1\]，同理往前计算长度，可以得出最前元素的下标是i-p\[i-1\]，更新最前元素的值p\[i-p\[i-1\]\]+=len;

然后更新最后元素的值为最前元素的值相同:p\[i+p\[i+1\]\]=p\[i-p\[i-1\]\],同时判断是否该值大于最大值并更新就行了，需要注意的是更新完首尾，如果当前数字的p\[i\]还是0，那么要修改为1。

代码:

class Solution {
    public:
        int longestConsecutive(vector<int>& nums) {
            map<int,int>p;
            int maxlen=0;
            for(int i=0;i<nums.size();i++)
            {
                int t=nums[i];
                if(p[t])
                {
                    continue;
                }
                int len=1;
                int j=t+1;
                len+=p[t+1];
                j=t+p[t+1];
                int k=t-p[t-1];
                p[k]+=len;
                p[j]=p[k];
                if(p[k]>maxlen)
                    maxlen=p[k];
                if(!p[t])
                    p[t]=1;
            }
            return maxlen;
        }
    };