[编程题]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.

```    public int longestConsecutive(int[] num) {
Set<Integer> set = new HashSet<Integer>();
for(int n : num){
}
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;
}```

```//用散列表，首先将数字都映射到散列表上，然后，对于每个数字，找到后就删除，然后向两边
//同时搜，只要搜到了就删除，最后求出长度。哈希表搜是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;
}
};```

```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)的范围

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;
}
};```

```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;
}
};```

```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;
}
};```

```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;
}
};
```

``````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;
}
};
``````

```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;
}
}
```

```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;
}
};```

//哈希集合 对于判断过的元素 从集合中删除
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++){

}

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;

}
}

```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){
}
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;
}
}```

`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)
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;
}
}

```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;
}
};```

```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;
}
};```

```    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;
}```

```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;
}
};
```

```/*
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;
}
};
```

```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;
}
};

```

```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;
}```

97条回答 27223浏览

# 相关试题

• 扫描二维码，关注牛客网

• 下载牛客APP，随时随地刷题