获取一个数组中最长的连续的元素序列

2017-01-05 20:04:38来源:CSDN作者:qq_34485658人点击

题目描述:获取一个数组中最长的元素序列。例如,给定了[31,6,32,1,3,2],其中最长的连续的元素序列是[1,2,3],最后返回其长度3

分析:判断当前节点是属于一个序列的,只需判断前一个或者后一个节点也在序列中即可,即判断array[i]-1和array[i]+1也是位于这个序列中即可。如果这样判断的话,就需要保存过程中的部分值,为此,可以采用哈希表来保存计算的中间值。


参考解答:

#include "stdafx.h"
#include<iostream>
#include<unordered_map>
#include<vector>
using namespace std;


struct Bound
{
int low;
int high;
Bound(int h=0,int l=0)
{
high=h;
low=l;
}
};


int lengthOfLongestConsecutiveSequence(vector<int> &num)
{
unordered_map<int,Bound> table;
int local;
int maxLen=0;


for(int i=0;i<num.size();i++)
{
if(table.count(num[i])){
continue;
}
local=num[i];
int low=num[i],high=num[i];
if(table.count(local-1)){
low=table[local-1].low;
}
if(table.count(local+1))
{
high=table[local+1].high;
}


table[low].high=table[local].high=high;
table[high].low=table[local].low=low;


if(high-low+1>maxLen)
{
maxLen=high-low+1;
}
}
return maxLen;
}


int _tmain(int argc, _TCHAR* argv[])
{
int arr[]={31,6,32,1,2,4};
vector<int> arr2(6);
for(int i=0;i<6;i++)
{
arr2.push_back(arr[i]);
}
int sum=lengthOfLongestConsecutiveSequence(arr2);
cout<<sum;
system("pause");
return 0;
}


最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台