Longest Consecutive Sequence

最近打算将做过的leetcode题也都总结下思路,感觉做算法题还是可以提高编程能力的。
最长连续序列题目如下:

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.

翻译一下就是:

有一个无序整型数组,找到数组中最长连续元素序列。
例如:[100, 4, 200, 1, 3, 2]中最长连续元素序列是[1, 2, 3, 4],所以返回结果是4.
算法复杂度要求0(n)

通过观察题目,我发现要找的连续元素序列不要求这些元素在原数组中必须是连续的。所以第一反应是排序,可是算法复杂度又要求O(n),排序这条路走不通了。
我比较搓,想了半天想不到好的办法,于是参考了网上资料,很有收获。基本思路是,以空间换时间。
基本思路:

  1. 扫描数组将数组中数据放入map中, key和value均为数组中的值。由于map中查找元素的时间复杂度是O(1),故以此牺牲空间,换取查询数组中元素的时间。
  2. 扫描数组,从第一个元素开始。然后对被扫描的元素做+1的操作,并利用map查找+1后的元素是否在map中。如果在则继续+1进行上述操作,如果不在则结束此方法。
  3. 对被扫描元素做-1操作,利用map查看-1后的元素是否在map中,后续判断逻辑同2.
  4. 将步骤2和3统计的长度相加,并与当前最长长度对比,如果大于当前最长长度,则更新最长长度。
  5. 遍历数组中每一个元素,并进行步骤2,3,4中的操作,遍历完成后就能得到最长连续数组长度。
    以上通过遍历一遍数组就能获得结果。
    时间复杂度计算:
    遍历数组存入map+遍历数组获得结果,两次遍历,时间复杂度在O(n)级别。

代码
根据上述思路可以写出代码。
第一部分,数组元素放入hashmap

1
2
3
4
5
6
7
8
9
10
11
private Map<Integer, Integer> array2Map(int [] nums){
Map<Integer, Integer> resultMap = new HashMap<>();
if(nums == null || nums.length == 0){
return resultMap;
}else{
for(int intNum : nums){
resultMap.put(intNum,intNum);
}
return resultMap;
}
}

第二部分,对数组中元素进行+1或者-1操作,查看+1或—1后的元素是否在数组中。并返回最长连续长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private int getLongestSubArray(int  intNum, Map<Integer, Integer> arrayMap, boolean plusOrMinus){
if(arrayMap == null || arrayMap.size() == 0){
return 0;
}
int tempLength = 0;
int tempNum = intNum;
while(arrayMap.containsKey(tempNum)){
tempLength ++;
if(plusOrMinus){
tempNum = tempNum + 1;
}else{
tempNum = tempNum -1;
}
}
return tempLength;
}

第三部分,方法主体,遍历数组得到最大连续数组长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int longestConsecutive(int[] nums) {
if(nums == null || nums.length == 0){
return 0;
}
Map<Integer, Integer> numsMap = array2Map(nums);
int maxLength = 0;
for(int intNum : nums){
int rightLength = getLongestSubArray(intNum, numsMap, true);
int leftLength = getLongestSubArray(intNum-1, numsMap, false);
if(maxLength < (rightLength + leftLength)){
maxLength = rightLength + leftLength;
}
}
return maxLength;
}

至此,算法基本实现。但是通过观察算法运行的过程就会发现,此算法存在重复计算的问题。例如,如果数组为[1,2,3,4],当对第一个元素1进行遍历时,对1加1,发现2也在数组中。对2进行遍历时,2减1发现1在数组中。对于整个计算来说,1发现2在数组中后,就确立了在此数组中1和2的连续关系,而且与2连续的肯定也与1连续。对于这种已经确定连续关系的元素,没必要再次进行遍历。
所以,可以在遍历1的时候,可将和1连续的所有数字,包括1本身从numsMap中删除。

根据以上思路修改代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private int getLongestSubArray(int  intNum, Map<Integer, Integer> arrayMap, boolean plusOrMinus){
if(arrayMap == null || arrayMap.size() == 0){
return 0;
}
int tempLength = 0;
int tempNum = intNum;
while(arrayMap.remove(tempNum)!=null){
tempLength ++;
if(plusOrMinus){
tempNum = tempNum + 1;
}else{
tempNum = tempNum -1;
}
}
return tempLength;
}

至此,此问题解决,提交后发现打败了80%的解决方案。runtime是11ms,还不错,不过还有比我这更牛逼的?于是翻阅了Discuss,然后给大神跪了。直接贴链接。用更加简洁的代码解决相同的问题。
不过还没太理解大神是如何想到这样的思路的。
自己再想想,想通了再更新。