【Leetcode】128.最长连续序列
【Leetcode】128.最长连续序列
Leetcode名企之路
发布于 2019-05-21 15:23:16
发布于 2019-05-21 15:23:16
题目
给定一个未排序的整数数组，找出最长连续序列的长度。
要求算法的时间复杂度为 O(n)。
示例:
输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。题解
这道题目最开始大家想的肯定是sort，然后计数计算最长序列。但是要求时间复杂度为：o(n)，就不能用sort了。一般在leetcode中，对时间复杂度有要求，就用空间来换，对空间复杂度有要求，就用时间来换。
基于这种思路我们就想要求最长的，就是要记录下有没有相邻的元素，比如遍历到100这个元素，我们需要查看[99, 101]这两个元素在不在序列中，这样去更新最大长度。而记录元素有没有这个事我们太熟悉了，用set这种数据结构，而set这种数据结构是需要o(n)的空间来换取的，这就是我们刚才说的用空间来换时间。
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> numsSet = new HashSet<>();
for (Integer num : nums) {
numsSet.add(num);
}
int longest = 0;
for (Integer num : nums) {
if (numsSet.remove(num)) {
// 向当前元素的左边搜索,eg: 当前为100, 搜索：99，98，97,...
int currentLongest = 1;
int current = num;
while (numsSet.remove(current - 1)) current--;
currentLongest += (num - current);
// 向当前元素的右边搜索,eg: 当前为100, 搜索：101，102，103,...
current = num;
while(numsSet.remove(current + 1)) current++;
currentLongest += (current - num);
// 搜索完后更新longest.
longest = Math.max(longest, currentLongest);
}
}
return longest;
}
}本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-05-20，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录