今日算法之_89_最长连续数列
前言
Github:https://github.com/HealerJean
1、最长连续序列
给定一个未排序的整数数组,找出最长连续序列的长度。
要求算法的时间复杂度为 O(n)。
示例:
输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
1.1、解题思路
先全部放到set集合中去,然后依次遍历数组,如果发现
num-1
不在set集合中,则一直知道num+1
,看看它是否也在集合中
1.2、算法
public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet();
for (int num : nums) {
set.add(num);
}
int maxLen = 0;
for (int num : set) {
if (!set.contains(num - 1)) {
int curLen = 1;
while (set.contains(num + 1)) {
curLen += 1;
num += 1;
}
maxLen = Math.max(maxLen, curLen);
}
}
return maxLen;
}
1.3、测试
@Test
public void test(){
int[] nums = {100,4,200,3,2};
System.out.println(longestConsecutive(nums));
}