# 小明思考

Just a software engineer
posts - 124, comments - 36, trackbacks - 0, articles - 0
BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

public class Solution {
public int longestConsecutive(int[] num) {
}
}

private static class Sequence{
int start;
int end;
int length;
}

public int longestConsecutive(int[] num) {
int len =0;
if(num==null || (len=num.length)<1){
return 0;
}

Map<Integer,Sequence> start = new HashMap<Integer,Sequence>();
Map<Integer,Sequence> end = new HashMap<Integer,Sequence>();
int maxLength = 0;

for(int i=0;i<len;++i){
Sequence s = null;
int v = num[i];
if(start.containsKey(v) || end.containsKey(v)){
continue;
}
if(start.containsKey(v+1)){
s = start.remove(v+1);
s.start = v;
++s.length;
while(end.containsKey(s.start-1)){ //merge ends
Sequence m = end.remove(s.start-1);
start.remove(m.start);
s.start = m.start;
s.length += m.length;
}
start.put(s.start, s);
}
else if(end.containsKey(v-1)){
s = end.remove(v-1);
s.end = v;
++s.length;
while(start.containsKey(s.end+1)){ //merge starts
Sequence m = start.remove(s.end+1);
end.remove(m.end);
s.end = m.end;
s.length += m.length;
}
end.put(s.end, s);
}
else{
s = new Sequence();
s.start = s.end = v;
s.length = 1;
start.put(v,s);
end.put(v,s);
}
//System.out.println(i+" "+v+" seqence:"+s.start+"/"+s.end+"/"+s.length);
if(maxLength<s.length){
maxLength = s.length;
}
}

return maxLength;
}

### 评论

I am afraid that the containsKey function is not O(1) operation.
additionally, this structure was merely O(n)
for(int i=0;i<len;++i){
while(end.containsKey(s.start-1)){ //merge ends

write in scala: (is it O(n) complexity?)

def maxSeq(lst: List[Int]): Int = {
val l = lst.sortWith(_ < _)
def findMax(ls: List[Int], maxLen: Int, curr: Int): Int = {
ls match {
case x :: y :: lst if x + 1 == y => findMax(y :: lst, if (maxLen > curr + 1) maxLen else curr + 1, curr + 1)
case x :: xs => findMax(xs, maxLen, 0)
case Nil => maxLen
}

}
findMax(l, 0, 0) + 1
}
def main(args: Array[String]): Unit = {
val lst = List(300, 1, 3, 2, 4, 5, 7, 9, 10, 22, 18, 6)
println(maxSeq(lst))
}
@Harry

Containkey of hashmap should be O(1) normally. In worst is O(n) when there are lots of hash conflicts.
@Harry

you're right. the sort function already is O(nlgn)... but I wonder that there is no such a solution to the problem with O(n) complexity.
any way, it is an interesting problem.

 只有注册用户登录后才能发表评论。 网站导航: 相关文章: