Skip to content

128. Longest Consecutive Sequence

难度:Hard

刷题内容

原题连接

  • https://leetcode.com/problems/longest-consecutive-sequence/

内容描述

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.

思路1 **- 时间复杂度: O(n)*- 空间复杂度: O(1)***

先对数组进行排序。在用unique()函数去除重复的数字。在遍历数组,找到最长的连续数字。时间复杂度为O(nlgn)。

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if(!nums.size())
            return 0;
        sort(nums.begin(),nums.end());
        auto end_pos = unique(nums.begin(),nums.end());
        int j = end_pos - nums.begin();
        int ans = 1,sum = 1;
        for(int i = 1;i < j;++i)
        {
            if(nums[i] == nums[i - 1] + 1)
                sum++;
            else
                sum = 1;
            ans = max(ans,sum);
        }
        return ans;
    }
};

思路2 **- 时间复杂度: O(nlgn)*- 空间复杂度: O(1)*** c++中的unordered_map是用hash桶实现的,所以可以在线性时间内完成。县遍历数组,用nums[i]作为unordered_map的键值。0作为 value。0表示此时的nums[i]还没被遍历过。接着遍历数组,用DFS搜索每个nums[i]的最长连续数字。被遍历过的nums[i]的unordered_map值设为1

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if(!nums.size())
            return 0;
        unordered_map<int,int> m;
        for(int i = 0;i < nums.size();++i)
            m[nums[i]] = 0;
        int ans = 0;
        for(int i = 0;i < nums.size();++i)
        {
            if(m[nums[i]])
                continue;
            m[nums[i]] = 1;
            int temp = nums[i] + 1,sum = 0;
            while(m.find(temp) != m.end())
                m[temp++] = 1;
            sum = temp - nums[i];
            temp = nums[i] - 1;
            //cout << temp << endl;
            while(m.find(temp) != m.end())
                m[temp--] = 1;
            sum += (nums[i] - temp - 1);
            ans = max(ans,sum);
        }
        return ans;
    }
};


回到顶部