给定一个无序的整数类型数组，求最长的连续元素序列的长度。
例如：
给出的数组为[1000, 4, 2000, 1, 3, 2],
最长的连续元素序列为[1, 2, 3, 4]. 返回这个序列的长度：4
你需要给出时间复杂度在O（n）之内的算法
[编程题]最长的连续元素序列长度
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:
- 跟牛客讨论区的答案不太一样
- 思想就是空间换时间，用map来保存每个数字的最长序列长度。
- 当访问到num[i]，令num[i]在map中的对应的序列长度为1，并查找左右两个数字是否已经存在map中。比如，map[num[i]-1]已经存在，num[i]对应的最长序列长度应该为num[i]-1的序列最长长度+1。右边的数字同理。
- 注意！应该修改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)
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)
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)
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)
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)
问题信息
难度：
113条回答
177收藏
37230浏览
通过挑战的用户
查看代码-
2023-02-15 15:30:38
-
2023-02-14 10:32:50 -
2022-09-13 16:23:41 -
2022-09-10 23:41:54 -
2022-09-09 15:32:57
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
