题目链接 : https://leetcode-cn.com/problems/longest-consecutive-sequence/
题目描述:
给定一个未排序的整数数组,找出最长连续序列的长度。
要求算法的时间复杂度为 O(n)。
示例:
输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
思路:
这道题, 难在时间复杂度限定在\(O(n)\), 要不排序就可以了!
思路一:集合
集合,查询时间复杂度为\(O(1)\)
思路二:字典
遍历数组, 用字典(哈希)记录目前与该值可以组成最长连续序列.
直接看代码(有注释)
代码:
思路一:
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
nums = set(nums)
res = 0
for num in nums:
# 判断是否是第一个数字
if num - 1 not in nums:
tmp = 1
while num + 1 in nums:
num += 1
tmp += 1
res = max(res, tmp)
return res
java
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> num_set = new HashSet<>();
for (int n : nums) num_set.add(n);
int res = 0;
for (int num : num_set) {
if (!num_set.contains(num - 1)) {
int tmp = 1;
while (num_set.contains(num + 1)) {
tmp++;
num++;
}
res = Math.max(res, tmp);
}
}
return res;
}
}
思路二:
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
# 记录首尾值的最长长度
lookup = {}
res = 0
for num in nums:
if num not in lookup:
# 判断左右是否可以连起来
left = lookup[num - 1] if num - 1 in lookup else 0
right = lookup[num + 1] if num + 1 in lookup else 0
# 记录长度
lookup[num] = left + right + 1
# 把头尾都设置为最长长度
lookup[num - left] = left + right + 1
lookup[num + right] = left + right + 1
res = max(res, left + right + 1)
return res
java
class Solution {
public int longestConsecutive(int[] nums) {
HashMap<Integer, Integer> lookup = new HashMap<>();
int res = 0;
for (int num : nums) {
if (!lookup.containsKey(num)) {
// 查看左右两边是否可以相连
int left = (lookup.containsKey(num - 1)) ? lookup.get(num - 1) : 0;
int right = (lookup.containsKey(num + 1)) ? lookup.get(num + 1) : 0;
lookup.put(num, left + right + 1);
// 改变首尾两个长度(换成更长的长度)
lookup.put(num - left, left + right + 1);
lookup.put(num + right, left + right + 1);
res = Math.max(res, left + right + 1);
}
}
return res;
}
}