LeetCode 128 Longest Consecutive Sequence

本文主要是介绍LeetCode 128 Longest Consecutive Sequence，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in \(O(n)\) time.

Solution

既然不能排序，那就用 \(set\) 将元素全部存进去。从所有可能序列中的最小开始遍历，逐次递增，然后更新最大值

class Solution {
private:
    unordered_set<int> s;
    int ans=0;
public:
    int longestConsecutive(vector<int>& nums) {
        for(auto ele:nums){
            s.insert(ele);
        }
        for(auto ele:nums){
            int cur = ele;
            if(!s.count(cur-1)){
                int cnt=1;
                while(s.count(cur+1)){
                    cur++;cnt++;
                }
                ans=max(ans, cnt);
            }
        }
        return ans;
    }
};

这篇关于LeetCode 128 Longest Consecutive Sequence的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！