124. Longest Consecutive Sequence

Leave a comment

September 3, 2016 by oneOokay

没想出来O(n)的算法,只能想到超级复杂的。看了答案用hashset还挺简单的,大概的了解一下记一下吧

public int longestConsecutive(int[] num) {
// write you code here
HashSet<Integer> set = new HashSet<Integer>();

for (int i = 0; i < num.length; i ++) {
set.add(num[i]); //把所有元素存到hashset中
}
int longest = 0;
for (int i = 0; i < num.length; i ++) {
int down = num[i] – 1; //找num[i]小的consequence
while (set.contains(down)){
set.remove(down); //在hash表中存在的话,remove,再继续找下一个比它小的consequence
down –;
}
int up = num[i] + 1; //同样的找比num[i]大的consequence
while (set.contains(up)){
set.remove(down);
up ++;
}
longest = Math.max(longest, up – down – 1);
}
return longest;
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: