128. Longest Consecutive Sequence

发表于 | 分类于

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.

解法1：

复杂度要求比较高，算来算去能用的也只有HashMap了。这个解法不太常见，用一个map存储一个range。
对于任意一个数，low和high都是数字本身。然后在map之内寻找下限和上限。寻找到之后更新res。
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        int res = 0;
        for (int num : nums) {
            if (map.containsKey(num)) continue;
            int low = num;
            int high = num;
            if (map.containsKey(num - 1)) low = map.get(num - 1);
            if (map.containsKey(num + 1)) high = map.get(num + 1);
            res = Math.max(res, high - low + 1);
            map.put(num, num);
            map.put(low, high);
            map.put(high, low);
        }
        return res;
    }
}

解法2：

这个解法清楚多了，首先把所有数据加入一个hashset. 之后对于每一个数，往下以及往上找到所有在set中的数据。 然后更新一下range。
Java

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
public class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        HashSet<Integer> set = new HashSet<Integer>();
        for (int num : nums) {
            set.add(num);
        }
        int res = 0;
        for (int num : nums) {
            int down = num - 1;
            while (set.contains(down)) {
                set.remove(down);
                down--;
            }
            int upper = num + 1;
            while (set.contains(upper)) {
                set.remove(upper);
                upper++;
            }
            res = Math.max(res, upper - down - 1);
        }
        return res;
    }
}

解法3: DFS –> StackOverflow

这个解法空间浪费很严重。。不过也是一种思路。leetcode上会stack overflow

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
class Solution {
    int count = 0;
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        for (int num : nums) {
            dfs(set, num);
        }
        return count;
    }
    private int dfs(Set<Integer> set, int current) {
        if (!set.contains(current)) return 0;
        set.remove(current);
        int smaller = dfs(set, current - 1);
        int bigger = dfs(set, current + 1);
        count = Math.max(smaller + bigger + 1, count);
        return smaller + bigger + 1;
    }
}