LeetCode 128 - Longest Consecutive Sequence

作者 QIFAN 日期 2016-12-24
LeetCode 128 - Longest Consecutive Sequence

原题链接:128. Longest Consecutive Sequence


题目

给定一串乱序数字数组,找到最长连续区间的长度,要求时间复杂度为 $O(n)$
举例:
[100, 4, 200, 1, 3, 2]
返回:4 (因为最长区间为[1, 2, 3, 4]

思路

由于要使用 $O(n)$ ,所以不能排序。

$O(n)$ 意味着只能进行常数项的遍历,而找连续时通常需要查找上一个与下一个,为查找而生的数据结构就是 Map

既然选择了 Map ,那就要确定 key 和 value 。key 一般就是数字本身了,value 的确定过程有点 tricky 。

我首先想到的是 union-find ,因为连续的数字区间可以看成一个 cluster ,cluster 中的所有值都相同,也就是该连续区间的长度。但是,这就意味着,每一次新数字的加入就要将 cluster 中的所有值都更新一遍,最坏情况下肯定不能满足 $O(n)$ 的要求。

然后我又想如果将值变成连续区间的第一个数字,这样也不行,因为只能确定头部,无法连接后方连续区间。只记录尾部数字也是同样的问题。所以怎么样可以头尾兼顾,又只需常数项的修改时间呢?

那就是只改头部与尾部,cluster 再大,也只有一头一尾,不会随着长度而改变。只要将头尾数字的值改为该区间的长度,那样就能根据长度推算出相应的头尾。

方法是这样的:
step 1: 查找 n
case 1: 若数字 n 不存在,当前长度 l = 1,则先查找 i - 1,再查找 i + 1
case 1.1: i - 1 存在,得到长度为 l’ ,将当前长度变为 l = l’ + l,更改头部的值也为 l ,接着去查找 i + 1
case 1.2: i - 1 不存在,当前长度为 l
case 1.3: i + 1 存在,得到长度 l’’ ,当前长度 l = l’’ + l,更改头尾部值为 l
case 1.4: i + 1 不存在,当前长度为 l
case 2: n 存在,不操作
step 2: 插入 (n, l)

最后可以通过遍历来确认最大连续,或者在插入过程中用一个变量来追踪最大值也可以,都是满足 $O(n)$

代码:

public int longestConsecutive(int[] nums) {
Map<Integer, Integer> numMap = new HashMap<>();
int longest = 0;
for (int i = 0; i < nums.length; i++) {
int tempLength = 1;
// 设置首位数字
int head = nums[i];
int tail = nums[i];
// 如果 Map 中不存在
if (numMap.get(nums[i]) == null) {
// 1 放入 map
numMap.put(nums[i], tempLength);
// 2.1 如果前一位存在
if (numMap.get(nums[i] - 1) != null) {
// 找到前一位所在连续的头部,并更新新的长度
head = (nums[i] - 1) - numMap.get(nums[i] - 1) + 1;
tempLength += numMap.get(nums[i] - 1);
}
// 2.2 如果后一位存在
if (numMap.get(nums[i] + 1) != null) {
// 找到后一位所在的连续区间的尾部,并更新长度
tail = nums[i] + 1 + numMap.get(nums[i] + 1) - 1;
tempLength += numMap.get(nums[i] + 1);
}
// 3 更新新的连续区间的长度
numMap.put(head, tempLength);
numMap.put(tail, tempLength);
longest = Math.max(longest, tempLength);
}
}
return longest;
}