熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> Java編程 >> Java核心技術 >> 正文

最長連續序列問題

2013-11-23 19:28:41  來源: Java核心技術 

  問題

  給定一個未排序的整數數組求最長的連續序列的長度要求算法的時間復雜度在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
  • 上一篇文章:

  • 下一篇文章:
  • 推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.