最长连续序列

给定一个未排序的整数数组,找出最长连续序列的长度。
要求算法的时间复杂度为 O(n)。
示例:
输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
解法一:
暴力解法,先对数组排序,然后对数组去重,然后再遍历数组找最长的连续序列,因为排序的时间复杂度无法达到O(N),所以不符合题目要求;
解法二:
采用hashset(元素不可重复)第一次遍历完成去重;
第二次遍历的过程中,不断寻找num-1和num+1;获取最大长度,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static int longestConsecutive(int[] arr) {
        if(arr.length == 0 || arr == null)
            return 0;
        HashSet<Integer> hs = new HashSet<>();
        for(int i = 0;i<arr.length;i++) {
            hs.add(arr[i]);
        }
        int max = 0;
        for(int i = 0;i<arr.length;i++) {
            if(hs.remove(arr[i])) {
                int pre = arr[i]-1;
                int next = arr[i]+1;
                while(hs.remove(pre))
                    --pre;
                while(hs.remove(next))
                    ++next;
                max = Math.max(max, next-pre-1);
            }
        }
        return max;
    }
0 条评论
发表一条评论