LeetCode: 最长连续序列
2019-02-24 本文已影响122人
一萍之春
最长连续序列(困难)
题目叙述:
给定一个未排序的整数数组,找出最长连续序列的长度。
要求算法的时间复杂度为 O(n)。
示例:
输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
解题思路:
方法一:
这个思路比较简单,但不是我本人推荐的一个方式,那就是将所有的元素进行一次排序,然后就从头开始遍历统计,取最大的值,这个方法如果算上排序的时间复杂度是O(nlogn)但是它反而是LeetCode上最快的方式。
代码实现:
class Solution {
public int longestConsecutive(int[] nums) {
if (nums == null || nums.length == 0) return 0;
Arrays.sort(nums);
int max = 1;
int cur = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] == nums[i-1]) continue;
if (nums[i] == nums[i-1] + 1) {
cur++;
} else {
cur = 1;
}
max = Math.max(max, cur);
}
return max;
}
}
方法二:
这个思路就是按照题意的时间复杂度的来做的,我们将用一个Set的集合将所有的元素都存起来。大家都知道Set的查找效率是O(1)。然后我们遍历Set将如果没有一个比他小1的元素之后,找出以它为起始的连续的序列的长度。时间复杂度为O(n)但是LeetCode运行时间比方法一的时间要长。个人揣测出题人的意思应该是这种类似的方法吧,不然不会被定为困难。
实现代码
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> numSet = new HashSet<Integer>();
for (int num : nums) {
numSet.add(num);
}
int max = 0;
for (int num : numSet) {
if (!numSet.contains(num-1)) {
int currentNum = num;
int cnt = 1;
while (numSet.contains(currentNum+1)) {
currentNum += 1;
cnt += 1;
}
max = Math.max(max, cnt);
}
}
return max;
}
}