首页 > 代码库 > [leetcode]Longest Consecutive Sequence

[leetcode]Longest Consecutive Sequence

2024-07-16 07:25:58   219人阅读

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：数组元素可能重复，比如-1,0,0,1,2.本以为重复就不算联系，答案应该是3，结果是4。你妹的

坑2：允许负数，这个没考虑实在不应该。

坑3：大数可能是Integer.MIN_VALUE，因此用计数排序的时候要注意考虑溢出

 

算法思路：

思路1：计数排序；线性排序算法，再求出最长连续序列长度。

没有做到bug-free，因此不贴了。

思路2：发散法，遇到一个数字，则想两端发散，并维护最大长度。

 1 public class Solution {     2     public int longestConsecutive(int[] num) { 3         if (num == null || num.length == 0) 4             return 0; 5         Set<Integer> set = new HashSet<Integer>(); 6         int max = 1; 7         for (int tem : num) { 8             set.add(tem); 9         }10         for (int tem : num) {11             if (set.contains(tem)) {12                 set.remove(tem);13                 int len = 1;14                 int post = tem + 1;15                 while (set.contains(post)) {16                     set.remove(tem);17                     post++;18                     len++;19                     max = Math.max(max, len);20                 }21                 int pre = tem - 1;22                 while (set.contains(pre)) {23                     set.remove(pre);24                     pre--;25                     len++;26                     max = Math.max(max, len);27                 }28             }29         }30         return max;31     }32 33 }

还可以用递归实现。大数据效率略低，不再实现了。时间、空间复杂度都是O(n)。

 


联系
我们