Lexi's Leetcode solutions

[leetcode] Longest Consecutive Sequence | 数组里整数能连起来的最长长度

Posted on: July 21, 2013

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

这个算法挺难想到的。让O(n)说明不能sort,那只能用container。但是用container怎么traverse连续的呢?又不能sort key。所以,我们人眼是怎么做这个题的呢,上来是100,我们其实就想找99和101,有的话就接着那个方向,直到找不着了为止。这样算过的数就从set里删掉,既然是别人的连续,那也是自己的连续,所以不用看了。这样过一遍就能把所有连续数列找全,没有元素重复处理的。

public int longestConsecutive(int[] num) {
    int res = 0;
    Set<Integer> set = new HashSet<Integer>();
    for (int i : num)
        set.add(i);
    for (int i = 0; i < num.length && !set.isEmpty(); i++) {
        int len = 0;
        //go up
        for (int j = num[i] - 1; set.contains(j); j--) {
            set.remove(j);
            len++;
        }
        //go down
        for (int j = num[i]; set.contains(j); j++) {
            set.remove(j);
            len++;
        }
        res = Math.max(res, len);
    }
    return res;
}
Advertisements
Tags:

5 Responses to "[leetcode] Longest Consecutive Sequence | 数组里整数能连起来的最长长度"

写得好

for (int i = 0; i < num.length && !set.isEmpty(); i++)
这个for loop改成iterate set会不会效率要高点。

问个naive的问题啊,set.contains(j)的时间复杂度是什么呢?

取决于是什么set,若是hashset的话就是1

多谢(●’◡’●)

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 )

Google+ photo

You are commenting using your Google+ 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 )

w

Connecting to %s

Blog Stats

  • 217,999 hits
July 2013
M T W T F S S
    Aug »
1234567
891011121314
15161718192021
22232425262728
293031  
Advertisements
%d bloggers like this: