首页 > 试题广场 > longest-consecutive-sequence
[编程题]longest-consecutive-sequence


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.


Ron头像 Ron
    public int longestConsecutive(int[] num) {
        Set<Integer> set = new HashSet<Integer>();
        for(int n : num){
        	set.add(n);
        }
        int max = 1;
        for(int n : num){
        	if(set.remove(n)){
        		int val = n;
        		int sum = 1;
        		int val_small = val - 1;
        		int val_big = val + 1;
        		while(set.remove(val_small)){
        			sum++;
        			val_small--;
        		}
        		while(set.remove(val_big)){
        			val_big++;
        			sum++;
        		}
        		max = Math.max(max, sum);
        	}
        }
        return max;
    }

发表于 2016-07-09 10:59:21 回复(13)
//用散列表,首先将数字都映射到散列表上,然后,对于每个数字,找到后就删除,然后向两边
//同时搜,只要搜到了就删除,最后求出长度。哈希表搜是O(1),因为每个数字只会添加一次,
//删除一次,所以复杂度是O(n)

class Solution {
public:
    int longestConsecutive(vector<int> &num) {
            unordered_set<int> st(num.begin(),num.end());
            int ans=0;
            for(auto v:num){
                if(st.find(v)==st.end()) continue;
                int l=v,r=v;
                st.erase(v);
                while(st.find(r+1)!=st.end()) st.erase(++r);
                while(st.find(l-1)!=st.end()) st.erase(--l);
                ans=max(r-l+1,ans);
            }
            return ans;
    }
};

发表于 2017-07-25 16:46:32 回复(0)
import java.util.*;
public class Solution {
    public int longestConsecutive(int[] num) {
        HashMap<Integer,Boolean> map = new HashMap<Integer,Boolean>();
		int max = -1;
		int count = 0;
		for (Integer integer : num) {
			map.put(integer,false);
		}
		Iterator<Integer> iterator = map.keySet().iterator();
		while(max<map.size()/2&&iterator.hasNext()){
			Integer integer = iterator.next();
            if(map.get(integer))
				continue;////该integer访问过了;
			int temp = integer;
			//先找左边
			while(map.containsKey(integer)){
				map.put(integer, true);//该integer访问过了;
				integer = integer-1;
				count++;
			}
			integer = temp+1;
			//找右边
			while(map.containsKey(integer)){
				map.put(integer, true);//该integer访问过了;
				integer = integer+1;
				count++;
			}
			if(count>max){
				max = count;
			}
			count = 0;
		}
        return max;
    }
}
HashMap元素存取的时间复杂度一般是O(1)的范围
编辑于 2016-05-31 13:31:35 回复(7)
hash表来解决这个问题,先初始化一个hash表, 存储所有数组元素, 然后遍历这个数组, 对找到的数组元素, 去搜索其相连的上下两个元素是否在hash表中, 如果在, 删除相应元素并增加此次查找的数据长度, 如果不在, 从下一个元素出发查找。已经访问过的元素记录下来或者删除,因为访问过的长度已经知道了额
class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        unordered_set<int> myset(num.begin(),num.end());
        int res=1;
        for(int current:num)
        {
            if(myset.find(current)==myset.end()) continue;
            
            myset.erase(current);
            int prev=current-1,post=current+1;
            while(myset.find(prev)!=myset.end())
            {
                myset.erase(prev--);
            }
            while(myset.find(post)!=myset.end())
            {
                myset.erase(post++);
            }
            res=max(res,post-prev-1);
        }
        
        return res;
    }
};

发表于 2016-07-14 20:17:13 回复(1)
class Solution {
//主要思路是用set存储num中的元素(去除重复元素不影响求解结果),
//然后寻找每个元素左右邻居数,删除,记录删除过程中最大连续长度
public:
    int longestConsecutive(vector<int> &num) {
        if(num.size()==0)
            return 0;
        set<int> st(num.begin(),num.end());
        int count = 1;
        for(int i=0;i<num.size();i++)
        {
            int tmp = num[i];
            if(st.count(tmp)==0)
               continue;
            int l=tmp-1,r=tmp+1;
            while(st.count(l))
               st.erase(l--);
            while(st.count(r))
               st.erase(r++);
            count = max(count,r-l-1);
        }
        return count;
    }
};

发表于 2018-07-14 21:07:30 回复(0)
class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        set<int> Set(num.begin(),num.end());
        int result = 1;
        for(int x:num)
        {
        	if(Set.find(x) == Set.end())
        		continue;
        	Set.erase(x);
        	int l=x-1,r=x+1;
        	while(Set.find(l) != Set.end())
        		Set.erase(l--);
        	while(Set.find(r) != Set.end())
        		Set.erase(r++);
        	result = max(result,r-l-1);
		}
		return result;
    }
};

发表于 2017-09-02 01:20:46 回复(0)
class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        if(num.size()==0) return 0;
        map<int,int> book;
        int i,res=0;
        for(i=0;i<num.size();i++) book[num[i]]=1;
        for(i=0;i<num.size();i++){
            int number=num[i],l,r;
            if(!book.count(number)) continue;
            book.erase(number);
            for(r=number+1;book.count(r);book.erase(r),r++);
            for(l=number-1;book.count(l);book.erase(l),l--);
            res=max(res,r-l-1);
        }
        return res;
    }
};

发表于 2018-05-27 14:51:26 回复(0)

首先将所有的元素记录在一个哈希表当中,然后从左到右依次遍历数组,假设遍历到元素cur,从cur开始向外扩张,记录能扩张出去的最大长度。每访问一个元素就将该元素在哈希表中抹去,这样可以保证每个元素插入一次、删除一次,时间复杂度为O(N)。如果每次访问不删除元素,也没有问题,但是时间复杂度就退化为O(N^2)。

class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        if(num.size() < 2)
            return num.size();
        unordered_set<int> sets(num.begin(), num.end());
        int res = 0;
        for(auto cur : num)
        {
            if(!sets.count(cur))
                continue;
            int left = cur;
            int right = cur;
            sets.erase(cur);
            while(sets.count(left-1))
            {
                sets.erase(--left);
            }
            while(sets.count(right+1))
            {
                sets.erase(++right);
            }
            res = max(res, right - left + 1);
        }
        return res;
    }
};
发表于 2018-03-30 20:01:14 回复(0)
import java.util.HashMap;
public class Solution {
    //利用map的查找时间为o(1)的特性,拿空间换时间
    public int longestConsecutive(int[] num) {
        if(num==null||num.length==0){
            return 0;
        }
        if(num.length==1){
            return 1;
        }
        HashMap<Integer,Boolean>map=new HashMap<>();
        for(int i=0;i<num.length;++i){//将数组里的数存储进map
            map.put(num[i],true);
        }
        int pre;//当前数的前一个数
        int curr;//当前数
        int post;//后一个数
        int max=1;//暂时的最大连续值
        int maxmax=max;//我们记录的当前最大的连续值
        for(int i=0;i<num.length;++i){
            if(map.get(num[i])==true){//还未被访问
            curr=num[i];
            pre=num[i]-1;
            post=num[i]+1;
            while(map.containsKey(pre)){//一直找前面那个数
                map.put(pre,false);//置值为false,下次不用再访问
                max++;//最大连续数加一
                pre--;//前面的那个数的数值减一
            }
            while(map.containsKey(post)){//同上
                map.put(post,false);
                max++;
                post++;
            }
                if(max>maxmax){//两个循环结束后,判断当前的最大连续值是否大于咱们存储的那个最大连续值
                    maxmax=max;
                }
                max=1;//置max为1
            }
        }
        return maxmax;
    }
}

发表于 2017-12-14 21:46:02 回复(1)
class Solution {
public:
    int longestConsecutive(vector<int> &num) {
    	priority_queue<int> prique;
    	for (unsigned int i = 0; i < num.size(); ++i) {
    		prique.push(num[i]);
    	}
    	int sum = 1;
    	int pre = prique.top();
    	prique.pop();
    	int cur = 0;
    	int curSum = 1;
    	while (!prique.empty()) {
    		cur = prique.top();
    		if (cur == pre-1) {
    			++curSum;
    			pre = cur;
    		}
    		else if (cur == pre) {
    			;
    		}
    		else {
    			if (curSum > sum) {
    				sum = curSum;
    			}
    			curSum = 1;
    			pre = cur;
    		}
    		prique.pop();
    	}
    	if (curSum > sum) {
			sum = curSum;
		}
    	return sum;
    }
};
发表于 2017-09-05 20:30:01 回复(0)
//哈希集合 对于判断过的元素 从集合中删除
import java.util.HashSet;
public class Solution {
    public int longestConsecutive(int[] num) {
        if(num.length==0){
            return 0;
        }
        
        HashSet<Integer> set=new HashSet<Integer>();
            
        for(int i=0;i<num.length;i++){
            
            set.add(num[i]);
            
        }
        
        int max=Integer.MIN_VALUE;
        
        for(int i=0;i<num.length;i++){
            
            if(set.contains(num[i])){
                
                int temp=1;
                int k=num[i];
                
                while(set.contains(++k) ){                    
                    temp++;                    
                    set.remove(k);
                }
                      
                k=num[i];      
                      
                while(set.contains(--k) ){                    
                    temp++;                    
                    set.remove(k);
                }
                
                if(temp>max){
                    max=temp;
                }
                
            }

        }
        
        
        return max;
        
        
    }
}
发表于 2017-08-06 19:39:24 回复(0)
import java.util.*;
public class Solution {
       /**
     * 1.先把数字放到一个集合中,拿到一个数字,就往其两边搜索,得到包含这个数字的最长串,
     * 2.并且把用过的数字从集合中移除(因为连续的关系,一个数字不会出现在两个串中)。
     * 3.最后比较当前串是不是比当前最大串要长,是则更新。如此继续直到集合为空。
     * @param num
     * @return
     */
    public int longestConsecutive(int[] num) {
        if(num==null||num.length==0) return 0;
        int res=1;
        Set<Integer> numbers=new HashSet<>();
        for(int val:num){
            numbers.add(val);
        }
        while(!numbers.isEmpty()){
            int len=1;
            Iterator iterator=numbers.iterator();
            int cur=(int)iterator.next();
            numbers.remove(cur);
            int left=cur-1,right=cur+1;
            while (numbers.contains(left)){
                len++;
                numbers.remove(left--);
            }
            while(numbers.contains(right)){
                len++;
                numbers.contains(right++);
            }
            res=len>res?len:res;
        }
        return res;
    }
}

发表于 2017-07-12 15:58:53 回复(1)
import java.util.*; public class Solution {
    public int longestConsecutive(int[] num) {
        if(num == null)
            return 0;
        Set<Integer> set = new HashSet<Integer>();//空间换时间
        for(int n : num)//O(n)
            set.add(n);
        int max = 1;
        for(int n : num){ //O(n)
            if(set.remove(n)){
                int val = n;
                int sum = 1;
                int smallVal = val - 1;
                int bigVal = val + 1;
                while(set.remove(smallVal)){
                    sum++;
                    smallVal--;
                }
                while(set.remove(bigVal)){
                    sum++;
                    bigVal++;
                }
                max = Math.max(max, sum);
            }
        }
        return max;
    }
}
发表于 2017-06-11 16:49:51 回复(0)
class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        int len = num.size();
        sort(num.begin(),num.end());
        int max = 1;
        int cnt = 1;
        for(int i = 1; i < len; i++)
        {
            if(num[i-1]+1 == num[i])
                cnt++;
            else if(num[i-1] == num[i]) //注意重复元素
                ;
            else
            {
                if(cnt > max)
                    max = cnt;
                cnt =1;
            }
        }
        if(cnt > max)
             max = cnt;
        return max;
    }
};

发表于 2017-08-06 16:05:14 回复(0)
class Solution {
public:
    int longestConsecutive(vector &num) {
        unordered_set search(num.begin(),num.end());
        int len = 0;
        int len_max = 1;
        int min, max;
        for(int i:num){
            if(search.find(i) == search.end()) continue;
            min = i - 1;
            max = i + 1;
            while(search.find(min) != search.end()){
                search.erase(min);
                min--;
            }
            min++;
            while(search.find(max) != search.end()){
                search.erase(max);
                max++;
            }
            max--;
            len = max - min + 1;
            if(len > len_max) len_max = len;
        }
        return len_max;
    }
};
发表于 2019-07-13 01:28:30 回复(0)
    public int longestConsecutive(int[] num) {
        int result = 0;
        Map<Integer,Integer> map = new HashMap<>();
        for (int a: num) {
            if (!map.containsKey(a)){
                //获取左右边界对应的序列长度
                int left = map.getOrDefault(a-1,0);
                int right = map.getOrDefault(a+1,0);
                int len = left+right+1;
                result = len>result?len:result;
                map.put(a-left,len);
                map.put(a+right,len);
                //把num加入map中防止重复判断(关键在于将num加入keyset中, value可以是任意值)
                map.put(a,len);
            }
        }
        return result;
    }
编辑于 2019-07-11 12:51:07 回复(0)
设置一个记录最大长度的变量max和记录每个起点的最大长度flag,遍历数列一遍,即可。
class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        if(num.size()==0){
            return 0;
        }
        sort(num.begin(),num.end());
        int flag=1,max=1;
        int id=1;
        while(id<num.size()){
            if(num[id]==num[id-1]+1){
                flag++;
            }else if(num[id]!=num[id-1]){
                if(flag>max)
                    max=flag;
                flag=1;
            }
            id++;
        }
         if(flag>max)
               max=flag;
        return max;
    }
};

发表于 2019-07-09 00:00:21 回复(0)
/*
1、使用一个哈希表来存储当前数字作为端点的连续区间的长度;
2、从nums中取一个数num,如果该数字不再哈希表中,则取出num相邻两个数num-1,num+1;
3、如果num-1存在于哈希表中,对应的连续区间的长度为left,则该区间一定是以num-1作为右端点(num不在哈希表中)
4、同理,如果num+1存在于哈希表,对应的连续区间长度为right,该区间一定是以num+1作为左端点
5、故新加入的点num对应的连续区间为left+right+1
*/
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_map<int,int> mp;
        int res=0;
        //初始化
        for(auto num:nums)
            mp[num]=0;
        for(int i=0;i<nums.size();i++){
            if(mp[nums[i]]<=0){
                //计算左节点
                int left=mp.count(nums[i]-1)<0?0:mp[nums[i]-1];
                //计算右节点
                int right=mp.count(nums[i]+1)<0?0:mp[nums[i]+1];
                //计算当前节点
                int curLen=left+right+1;
                if(curLen>res)
                    res=curLen;
                mp[nums[i]]=curLen;//mp[nums[i]]可以设为任意值不会有影响
                //更新端点值
                /*
                因为nums[i]-1,nums[i],nums[i]+1变成了nums[i]-left~nums[i]+right的内部节点,
                内部节点对下一个节点的更新不再起作用,所以不用更新nums[i]-left+1~nums[i]+right-1的
                连续序列的长度,但端点值对下一个节点的更新会起作用,所以需要每次更新端点节点
                */
                mp[nums[i]-left]=curLen;
                mp[nums[i]+right]=curLen;
            }
        }
        return res;
    }
};

发表于 2019-06-13 21:12:54 回复(0)
class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        map<int,bool> mp;
        //先将数组映射到map
        for(int i=0;i<num.size();i++){
            int val = num[i];
            mp[val] = true;
            //if(max<val) max=val;
        }
        
        int maxlen = 0;
        
        //分别向左右搜索,直到map中的值为false,map每次查找的复杂度是O(1),所以总的复杂度是O(1)
        for(int i=0;i<num.size();i++){
            int len = 0;
            int val=num[i];
            if(mp[val] == false) continue;
            int l = val, r=val+1;
            while(mp[l]){
                mp[l] = false;
                l -=1;
                len++;
            }
            while(mp[r]){
                mp[r] = false;
                r +=1;
                len++;
            }
            if(maxlen < len) maxlen=len;
        }
        return maxlen;
    }
};


发表于 2019-05-12 21:30:46 回复(0)
int longestConsecutive(vector<int> &num)
{
 int length = num.size();
 if (length == 0)
 {
  return 0;
 }
 sort(num.begin(), num.end());
 int res = 1;//至少是1
 int i = 0;
 while (i < length-1)
 {
  int cur_res=1;
  int j = i + 1;
  while ((num[j] == num[i]+1||num[j]==num[i])&&i<length-1)
  {
            if(num[j]==num[i]+1)
            {
                cur_res+=1;
            }
   i++;
            j++;
  }
  if (cur_res > res)
  {
   res = cur_res;
  }
  i = j;
 }
 return res;
}

发表于 2019-05-10 14:10:55 回复(0)