首页 > 试题广场 >

最长的连续元素序列长度

[编程题]最长的连续元素序列长度
  • 热度指数:29511 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
给定一个无序的整数类型数组,求最长的连续元素序列的长度。
例如:
给出的数组为[1000, 4, 2000, 1, 3, 2],
最长的连续元素序列[1, 2, 3, 4]. 返回这个序列的长度:4
你需要给出时间复杂度在O(n)之内的算法
示例1

输入

[1000, 4, 2000, 1, 3, 2]

输出

4
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 回复(19)
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 回复(6)
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)
  • idea:

    1. 跟牛客讨论区的答案不太一样
    2. 思想就是空间换时间,用map来保存每个数字的最长序列长度。
    3. 当访问到num[i],令num[i]在map中的对应的序列长度为1,并查找左右两个数字是否已经存在map中。比如,map[num[i]-1]已经存在,num[i]对应的最长序列长度应该为num[i]-1的序列最长长度+1。右边的数字同理。
    4. 注意!应该修改num[i]所在序列的最左最右元素的最长长度(序列要变长必须接触序列最左最右的元素,只需改变最左最右元素的最长长度)。
  • code:

#include <bits/stdc++.h>

class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        map<int, int> mp;
        int ans = 0;
        for (int i = 0; i < num.size(); i++){
            if (!mp.count(num[i])){
                mp[num[i]] = 1;
                int left = 0, right = 0;
                if (mp.count(num[i]-1)){
                    // 左边有序列
                        left = mp[num[i]-1]; //记录左边序列长度
                        mp[num[i]] += left; //当前序列长度加上左边序列长度
                }
                if (mp.count(num[i]+1)){
                        right = mp[num[i]+1];    //记录右边序列长度
                        mp[num[i]] += right;    //当前序列长度加上右边序列长度
                }
                mp[num[i]+right] = mp[num[i]]; //更新序列最右端元素的序列长度
                mp[num[i]-left] = mp[num[i]]; ////更新序列最左端元素的序列长度
                if (mp[num[i]] > ans) ans = mp[num[i]];
            }
        }
        return ans;
    };
};
发表于 2019-08-15 17:30:53 回复(1)
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 回复(3)
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(int[] nums) {
        //create a hashset, and put nums in it
        Set<Integer> tempSet = new HashSet<>();
        for(int element : nums){
            tempSet.add(element);
        }
        //set a flag
        int record = 0 ;

        //traverse the hashset
        for(int number : tempSet){
            //judge the exixtense of x-1
            if(!tempSet.contains(number-1)){
                int currentNum = number;
                int currentRecord=1;
                //if not contain x-1 ,calculate the currentRecord
                while(tempSet.contains(currentNum+1)){
                    currentRecord+=1;
                    currentNum+=1;
                }
                //keep the record always the Max one
                record=Math.max(record,currentRecord);
            }
        }
        return record;
    }
} 
       

发表于 2020-07-08 12:27:13 回复(1)
用它排序后 Arrays.sort(num); 时间复杂度能是O(n)么?

发表于 2020-05-20 18:10:09 回复(0)
class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        priority_queue<int> Q;
        for(auto elm:num)
            Q.push(elm);
        int n = 1, max_len = 1;
        while(!Q.empty()){
            int t = Q.top();
            Q.pop();
            cout << t << endl;
            if(!Q.empty() && Q.top() == t-1){
                n += 1;
                max_len = max(max_len, n);
            }
            if(!Q.empty() && Q.top()!=t-1){
                max_len = max(max_len, n);
                n = 1;
            }
        }
        return max_len;
    }
};

发表于 2020-05-13 21:07:52 回复(0)
import java.util.*;

public class Solution {
    /**
     *  本来先排序再遍历一遍即可,时间复杂度O(nlogn)
     *  但是题目要求O(n),就只能时间换空间,通过哈希表
     *  记录数组元素,然后遍历数组,去哈希表中找这个元
     *  素所处的连续序列,得到序列长度,这里注意已经找
     *  到的元素从哈希表中去除,不需要再次查找了,所有
     *  元素只会被遍历两次,时间复杂度O(n)
     */
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>(nums.length);
        for(int num:nums){
            set.add(num);
        }
        int max = 0;
        for(int num:nums){
            while(set.remove(num)){
                int left = num, right = num;
                while(set.remove(left-1)) left--;
                while(set.remove(right+1)) right++;
                max = Math.max(max, right-left+1);
            }
        }
        return max;
    }
}

发表于 2020-01-04 16:14:13 回复(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)
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)
//用散列表,首先将数字都映射到散列表上,然后,对于每个数字,找到后就删除,然后向两边
//同时搜,只要搜到了就删除,最后求出长度。哈希表搜是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 回复(2)
public int longestConsecutive (int[] num) {
        // write code here
        int count = 1;
        if(num.length == 0){
            return 0;
        }
        Set<Integer> set = new HashSet<>();
        for(int n : num){
            set.add(n);
        }
        for(int i = 0 ; i < num.length; i++){
            int temp = num[i];
            if(!set.contains(num[i])){
                continue;
            }
            int l = temp - 1;
            int r = temp + 1;
            while(set.contains(l)){
                set.remove(l--);
            }
            while(set.contains(r)){
                set.remove(r++);
            }
            count = Math.max(count, r - l - 1);
        }
        return count;

    }

发表于 2021-01-13 14:43:27 回复(0)