128 Longest Consecutive Sequence 一个无序整数数组中找到最长连续序列

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

给定一个未排序的整数数组，找出最长连续序列的长度。
例如，
给出 [100, 4, 200, 1, 3, 2]，
这个最长的连续序列是 [1, 2, 3, 4]。返回所求长度： 4。
要求你的算法复杂度为 O(n)。
详见：https://leetcode.com/problems/longest-consecutive-sequence/description/

Java实现：

方法一：

class Solution {
public int longestConsecutive(int[] nums) {
int res=0;
Set<Integer> s=new HashSet<Integer>();
for(int num:nums){
s.add(num);
}
for(int num:nums){
if(s.remove(num)){
int pre=num-1;
int next=num+1;
while(s.remove(pre)){
--pre;
}
while(s.remove(next)){
++next;
}
res=Math.max(res,next-pre-1);
}
}
return res;
}
}

方法二：

class Solution {
public int longestConsecutive(int[] nums) {
int res = 0;
Map<Integer, Integer> m = new HashMap<Integer, Integer>();
for (int num : nums) {
if (!m.containsKey(num)){
int pre = m.containsKey(num - 1) ? m.get(num - 1) : 0;
int next = m.containsKey(num + 1) ? m.get(num + 1) : 0;
int sum = pre + next + 1;
m.put(num, sum);
res = Math.max(res, sum);
m.put(num - pre, sum);
m.put(num + next, sum);
}
}
return res;
}
}