LeetCode: Longest Consecutive Sequence

LeetCode: Longest Consecutive Sequence 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

import static org.junit.Assert.assertSame;
/**
 * Description: Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
 * <p/>
 * For example, Given [100, 4, 200, 1, 3, 2], The longest consecutive elements sequence is [1, 2, 3, 4]. Return its
 * length: 4.
 * <p/>
 * Your algorithm should run in O(n) complexity.
 *
 * @author hzhou
 */
public class LongestConsecutiveSequence {
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return 1;
        }
        Set<Integer> set = new HashSet<Integer>();
        for (int i : nums) {
            set.add(i);
        }
        int result = 0;
        for (int i : nums) {
            int l = i - 1;
            int r = i + 1;
            int count = 1;
            while (set.contains(l)) {
                count++;
                set.remove(l);
                l--;
            }
            while (set.contains(r)) {
                count++;
                //set.remove(r);
                r++;
            }
            result = Math.max(result, count);
        }
        return result;
    }
    @Test
    public void test() {
        int[] nums = new int[]{2147483646, -2147483647, 0, 2, 2147483644, -2147483645, 2147483645};
        assertSame(3, longestConsecutive(nums));
    }
}