leetcode 128. Longest Consecutive Sequence 最长连续序列 + HashSet查找的方法

清疚 2022-06-08 05:36 134阅读 0赞

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.

这道题主要是要求时间复杂度是O(n)，那么排序是肯定不能用的了，自由实用set等结构才可能做出来，我在网上看了一个做法，做法很棒。

注意这道题的做法很棒，值得学习。

本题就是做一个查找，注意查找结束之后要删除相关元素

代码如下:

import java.util.HashSet;
    import java.util.Iterator;
    
    /*
     * 时间复杂度要求是O(n)，那么就不可能使用排序了
     * 我想到了使用set，但是没有想到具体的方法，网上看了一个方法，
     * 这个方法很不错
     * */
    public class Solution 
    {
        public int longestConsecutive(int[] nums) 
        {
            if(nums == null || nums.length<=0 )
                return 0;
            HashSet<Integer> set = new HashSet<>();
            for(int i=0;i<nums.length;i++)
                set.add(nums[i]);
    
            int maxLen = 0;
            while(set.isEmpty()==false)
            {
                Iterator<Integer> iter = set.iterator();
                int target = (int)iter.next();
                set.remove(target);
    
                int tmpLen=1;
                int i=target-1;
                while(set.contains(i))
                {
                    set.remove(i--);
                    tmpLen++;
                }
    
                i=target+1;
                while(set.contains(i))
                {
                    set.remove(i++);
                    tmpLen++;
                }
                maxLen=Math.max(maxLen, tmpLen);
            }
            return maxLen;
        }
    }

下面是C++的做法，看到O(n)的复杂度就应该想到使用set等数据结构，想清楚了做法就很简单了

**注意C++的set 遍历是BST的中序遍历，是有序的**

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    #include <iomanip>
    #include <cstdlib>
    #include <ctime>
    
    using namespace std;
    
    
    
    class Solution
    {
    public:
        int longestConsecutive(vector<int>& a)
        {
            set<int> s(a.begin(), a.end());
            int maxLen = 0;
            while (s.empty() == false)
            {
                int key = *(s.begin()), len = 1;
                s.erase(s.begin());
                while (s.find(key+1) != s.end())
                {
                    len++;
                    s.erase(key+1);
                    key++;
                }
                maxLen = max(maxLen, len);
            }
            return maxLen;
        }
    };