Leetcode 128最长连续序列

题目要求时间复杂度为O(n)，由此可见，排序肯定不行的。

在O（n）时间下第一个想到的就是哈希，这里可用Map解决。

怎么样找到连续的序列呢，可以用到并查集。

连续的序列为一个集合，在用个结构存放每个集合中元素个数就行了。

并查集具体的 *** 作过程：每遍历到一个数，就看集合中是否存在它前一个数，若存在，则他的父节点就为前一个数，按照这个思路排下去，每个集合中都是连续的。

本来这些都可用数组搞定，但是题目的数据范围为1e9，数组开不了那么大，只能用map了。

下面给出Leetcode和本地编译器的代码。

Leetcode

/*
 * @lc app=leetcode.cn id=128 lang=cpp
 *
 * [128] 最长连续序列
 */

// @lc code=start
#define INF 0x3f3f3f3f
struct deNum{
 int value = INF;//初始化为INF，因为默认的为0，但是又有0这个元素
};
struct deV{
 int cnt = 1;
};
map mp;//父节点Map key-》value（本节点，父节点）
map Max;//个数Map key-》value（本节点，本节点所在集合个数）
int findfa(int x)
{
   if(x != mp[x].value){
    mp[x].value = findfa(mp[x].value);
   }
   return mp[x].value;
}
void Union(int x,int y)
{
    int fax = findfa(x);
    int fay = findfa(y);
    if(fax != fay){
      mp[fax].value = fay;
      Max[fay].cnt += Max[fax].cnt;
    }

    //printf("x : %d, fa: %d\n",x,mp[x].value);
}
class Solution {
public:
    int longestConsecutive(vector& nums) {
        for(int i = 0; i < nums.size(); i++){
            mp[nums[i]].value = nums[i];
            Max[nums[i]].cnt = 1;
        }
        for(int i = 0; i < nums.size(); i++){
        if(mp[nums[i] - 1].value != INF && mp[nums[i]].value != INF){//验证集合中是否存在前一个数，存在，则合并
        Union(nums[i],nums[i] - 1);
      }
    }
        int MAX = 0;
        map::iterator iter;
        for(iter = Max.begin(); iter != Max.end(); iter++){
            MAX = max(MAX,iter->second.cnt);
        }
        mp.clear();
        Max.clear();  
        return MAX;

    }
};
// @lc code=end

编译器代码 可用来debug

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include