首页 > 代码库 > [Leetcode][JAVA] Longest Consecutive Sequence

[Leetcode][JAVA] 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.

 

有难度的一题,想不到HashMap的话很难去实现.

想象一个无穷长度的数组,下标可以为任意值,记录的是数组下标所在连续数字序列的长度,初始均为0。那么,当新进入一个数字X时,需要做以下事情:

1.把X对应的值置为1.

2.查看X-1的值,得到与X连着的左半部分长度,记为low

3. 查看X+1的值,得到与X连着的右半部分长度,记为high。

4. low+high+1 即为X所在连续数字序列的长度。如果比目前最大值大则更新。

5. 更新整个连续数字序列。

 

针对步骤5,还可以继续优化。对于这个问题,处于连续数字序列内部的值是没有意义的,因为新进入一个数字后我们只会考察与它相邻的位的情况,换句话说对于一个连续数字序列,只有处于两头的值才是有意义的,所以,每次更新数字序列长度时只要更新这两个值即可。

这两个值得下标为X-low 和X+high。

HashMap本质上也是个数组。与以上思路区别在于,无法初始为0,所以,在查看X-1和X+1之前,需要判断它们是否在HashMap中,不在则视为值为0.

最后,如果遇到相同数字则直接忽略。

代码:

 1     public int longestConsecutive(int[] num) { 2         HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>(); 3         int max = 0; 4         for(int i=0;i<num.length;i++) 5         { 6             if(hm.containsKey(num[i])) 7                 continue; 8             hm.put(num[i],1); 9             int low = hm.containsKey(num[i]-1)?hm.get(num[i]-1):0;10             int high = hm.containsKey(num[i]+1)?hm.get(num[i]+1):0;11             int v = low+high+1;12             hm.put(num[i]-low,v);13             hm.put(num[i]+high,v);14             max = Math.max(max,v);15         }16         return max;17     }

 

[Leetcode][JAVA] Longest Consecutive Sequence