题目
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1：
输入：nums = [100,4,200,1,3,2] 输出：4 解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2：
输入：nums = [0,3,7,2,5,8,4,6,0,1] 输出：9
解题
方法一：哈希表
class Solution { public: int longestConsecutive(vector<int>& nums) { unordered_set<int> set; for(int num:nums) set.insert(num);//去重 int res=0; for(int num:set){ if(!set.count(num-1)){//为了找到一个连续序列的起始位置 int cur_num=num; int cur_count=1; while(set.count(cur_num+1)){ cur_num++; cur_count++; } res=max(res,cur_count); } } return res; } };
方法二：并查集
class UnionFind{ private: vector<int> parent; vector<int> size; public: UnionFind(int n){ parent.resize(n); size.resize(n); for(int i=0;i<n;i++){ parent[i]=i; size[i]=1; } } int find(int index){ if(parent[index]==index) return index; return parent[index]=find(parent[index]); } void unite(int index1,int index2){ int p1=find(index1); int p2=find(index2); if(p1!=p2){ parent[p1]=p2; size[p2]+=size[p1]; size[p1]=0; } } int getMaxConn(){ int res=0; for(int i=0;i<size.size();i++){ res=max(res,size[i]); } return res; } }; class Solution { public: int longestConsecutive(vector<int>& nums) { int n=nums.size(); UnionFind uf(n); unordered_map<int,int> mp; for(int i=0;i<n;i++){ if(mp.count(nums[i])) continue; if(mp.count(nums[i]-1)){ uf.unite(i,mp[nums[i]-1]); } if(mp.count(nums[i]+1)){ uf.unite(i,mp[nums[i]+1]); } mp[nums[i]]=i; } return uf.getMaxConn(); } };
