|
问题 给定一个未排序的整数数组求最长的连续序列的长度要求算法的时间复杂度在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; } |
