最長連續序列問題

　　問題

　　給定一個未排序的整數數組求最長的連續序列的長度要求算法的時間復雜度在O(n)

　　比如對於數組[ ]其中最長序列為[]所以應該返回

　　public class Solution {

　　public int longestConsecutive(int[] num) {

　　//write your code here

　　}

　　}

　　解法思路

　　因為要求復雜度是O(n)可以考慮使用哈希表進行查詢使用兩個HashMap分別記錄序列的開始值和結束值遍歷數組如果發現比該元素大的開始值或者比改元素小的結束值均進行合並工作

　　不多說了看代碼

　　private static class Sequence{

　　int start;

　　int end;

　　int length;

　　}

　　public int longestConsecutive(int[] num) {

　　int len =;

　　if(num==null || (len=numlength)<){

　　return ;

　　}

　　Map<IntegerSequence> start = new HashMap<IntegerSequence>();

　　Map<IntegerSequence> end = new HashMap<IntegerSequence>();

　　int maxLength = ;

　　for(int i=;i<len;++i){

　　Sequence s = null;

　　int v = num[i];

　　if(ntainsKey(v) || ntainsKey(v)){

　　continue;

　　}

　　if(ntainsKey(v+)){

　　s = startremove(v+);

　　sstart = v;

　　++slength;

　　while(ntainsKey(sstart)){ //merge ends

　　Sequence m = endremove(sstart);

　　startremove(mstart);

　　sstart = mstart;

　　slength += mlength;

　　}

　　startput(sstart s);

　　}

　　else if(ntainsKey(v)){

　　s = endremove(v);

　　send = v;

　　++slength;

　　while(ntainsKey(send+)){ //merge starts

　　Sequence m = startremove(send+);

　　endremove(mend);

　　send = mend;

　　slength += mlength;

　　}

　　endput(send s);

　　}

　　else{

　　s = new Sequence();

　　sstart = send = v;

　　slength = ;

　　startput(vs);

　　endput(vs);

　　}

　　//Systemoutprintln(i+ +v+ seqence:+sstart+/+send+/+slength);

　　if(maxLength<slength){

　　maxLength = slength;

　　}

　　}

　　return maxLength;

　　}

From:http://tw.wingwit.com/Article/program/Java/hx/201311/26932.html