leetcode 128. 最长连续序列(并查集，unordered_map,unordered_set)

暴力

class Solution {
    
public:int longestConsecutive(vector<int>& nums) {
    int n=nums.size();sort(nums.begin(),nums.end());for(int i=0;i<n;i++)cout<<nums[i]<<" ";cout<<endl;int maxl=0;for(int i=0;i<n;i++){
       int lens=1;for(int j=i+1;j<n;j++){
    if(nums[j]==nums[j-1]+1)lens+=1;else if(nums[j]==nums[j-1])continue;elsebreak;}maxl=max(maxl,lens);}return maxl;}
};

class Solution:def longestConsecutive(self, nums: List[int]) -> int:nums=set(nums)maxm=0for x in nums:if x-1 not in nums:y=x+1while y in nums:y+=1maxm=max(maxm,y-x)return maxm

class Solution {
    
public:int longestConsecutive(vector<int>& nums) {
    unordered_set<int> numset(nums.begin(),nums.end());int best=0;int y;for( auto num:nums){
    //if 以num 开头if(numset.find(num-1)==numset.end()){
    y=num+1;while(numset.find(y)!=numset.end()){
    y+=1;}best=max(best,y-num);}}return best;}
};

unordered_set 用法参考：http://c.biancheng.net/view/549.html

实现的并查集

class Solution {
    
public:unordered_map<int,int> numsmap;//p较小元素，q较大元素int find(int p){
    if(p!=numsmap[p])numsmap[p]=find(numsmap[p]);return numsmap[p];}void uni(int p,int q){
    int pRoot=find(q);numsmap[p]=pRoot;}int longestConsecutive(vector<int>& nums) {
    for(auto num:nums){
    if(numsmap.count(num)==0){
    numsmap[num]=num;}}for(auto num:nums){
    if(numsmap.count(num-1)){
    uni(num-1,num);}}for(auto num:nums){
    if(numsmap.count(num+1)){
    uni(num,num+1);} }/ 以下部分用来输出最大的集合vector<int>temp(numsmap.size());auto iter=numsmap.begin();int i =0;while(iter!=numsmap.end()){
    temp[i]=iter->second;// cout<<iter->first<<":"<<iter->second;// cout<<endl;iter++;i++;}int best=0;unordered_map<int,int> times;times.clear();// cout<<"*******"<<endl;for(auto t:temp){
          times[t]+=1;best=max(best,times[t]);}return best;}
};