首页 > 代码库 > Leetcode: Longest Consecutive Sequence
Leetcode: 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.
先排序然后扫描一次，维护一个最长consecutive sequence长度这个方法很直接，但是至少需要O(NlongN). 不让排序，那就要想，估计得用空间来换取时间了。
把数字放到一个集合中，拿到一个数字，就往其两边搜索，看其两边是否在集合中，这样得到包含这个数字的最长串的长度，并且把用过的数字从集合中移除（因为连续的关系，一个数字不会出现在两个串中）。最后比较当前串是不是比当前最大串要长，是则更新。如此继续直到集合为空。如果我们用HashSet来存储数字，则可以认为访问时间是常量的，那么算法需要一次扫描来建立集合，第二次扫描来找出最长串，所以复杂度是O(2*n)=O(n)，空间复杂度是集合的大小，即O(n)。
这道题还用了Iterator: 10-11行
1 public class Solution { 2 public int longestConsecutive(int[] num) { 3 if (num==null || num.length==0) return 0; 4 HashSet<Integer> set = new HashSet<Integer>(); 5 for (int elem : num) { 6 set.add(elem); 7 } 8 int longest = 1; 9 while (!set.isEmpty()) {10 Iterator iter = set.iterator();11 int item = (int)iter.next();12 set.remove(item);13 int len = 1;14 int i = item - 1;15 while (set.contains(i)) {16 len++;17 set.remove(i--);18 }19 i = item + 1;20 while (set.contains(i)) {21 len++;22 set.remove(i++);23 }24 if (len > longest) longest = len;25 }26 return longest;27 }28 }
Leetcode: Longest Consecutive Sequence
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。