最长连续序列
给定一个未排序的整数数组,找出最长连续序列的长度
示例:
输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是[1, 2, 3, 4]。它的长度为 4
方法一:先排序
public int longestConsecutive(int[] nums) {
Arrays.sort(nums);
int maxSeq = 0;
for (int i = 0; i < nums.length; ) {
int[] ans = seq(nums, i);
maxSeq = Math.max(maxSeq, ans[0]);
i = ans[1];
}
return maxSeq;
}
public int[] seq(int[] nums, int start) {
int i = start + 1;
int[] ans = new int[2];
ans[0] = 1;
while (i < nums.length) {
if (nums[i] == nums[i - 1] + 1) {
ans[0]++;
i++;
} else if (nums[i] == nums[i - 1]) {//跳过重复元素
i++;
} else {
break;
}
}
ans[1] = i;
return ans;
}
时间复杂度O(nlogn)
方法二:暴力法
先将数字存到set中,再考虑数组中的每一个数字,从set中判断nums[i]+1...num[i]+k是否存在,并记录最长序列
public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int num : nums) {
set.add(num);
}
int maxSeq = 0;
for (int num : nums) {
int seq = 0;
while (set.contains(num)) {
seq++;
num++;
}
maxSeq = Math.max(maxSeq, seq);
}
return maxSeq;
}
时间复杂度O(n2)
存在重复的计算,如果数组 54367,当我们遇到 5 的时候计算一遍 567,遇到 4 又计算一遍 4567,遇到 3 又计算一遍 34567,很明显从 3 开始才是我们想要的序列。
换句话讲,我们只考虑从序列最小的数开始即可。实现的话,当考虑 n 的时候,我们先看一看 n - 1 是否存在,如果不存在,那么从 n 开始就是我们需要考虑的序列了。否则的话,直接跳过。
方法三:哈希表
public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int num : nums) {
set.add(num);
}
int maxSeq = 0;
for (Integer num : set) {
if (!set.contains(num - 1)) {//不连续的起始元素
int startNum = num;
int i = startNum + 1;
while (set.contains(i)) {//找连续的元素
i++;
}
maxSeq = Math.max(maxSeq, i - startNum);
}
}
return maxSeq;
}
时间复杂度O(n):外层循环需要 O(n)的时间复杂度,只有当一个数是连续序列的第一个数的情况下才会进入内层循环,然后在内层循环中匹配连续序列中的数,因此数组中的每个数只会进入内层循环一次
方法四
相比于方法二,在遍历的过程中set中元素删除,避免了重复计算
public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int num : nums) {
set.add(num);
}
int maxSeq = 0;
for (int num : nums) {
int seq = 0;
int cur = num;
while (set.remove(cur)) {//向前搜索连续的数字
seq++;
cur--;
}
cur = num + 1;
while (set.remove(cur)) {//向后搜索连续的数字
seq++;
cur++;
}
maxSeq = Math.max(maxSeq, seq);
}
return maxSeq;
}
时间复杂度O(n)
方法五:动态规划
本质上就是把连续的序列进行合并,思路就是考虑我们先解决了小问题,然后大问题怎么解决
如已经有了连续序列:
1 2 3 5 6 对应map 1->3 3->3 5->2 6->2
这时来了个4 4-1 4+1存在
1 2 3 4 5 6 1->6 3->3 5->2 6->6
这时来了7 7-1存在
1 2 3 4 5 6 7 1->7 3->3 5->2 6->6 7->7
public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<>();
Map<Integer, Integer> map = new HashMap<>();//k:数字 v:以k为边界的连续序列长度
int maxSeq = 0;
for (int num : nums) {
if (!set.contains(num)) {//跳过重复元素
set.add(num);
int leftLen = map.getOrDefault(num - 1, 0);//获得以num-1为边界的连续序列长度
int rightLen = map.getOrDefault(num + 1, 0);
int len = leftLen + 1 + rightLen;
map.put(num - leftLen, len);//更新左右边界长度
map.put(num + rightLen, len);
maxSeq = Math.max(maxSeq, len);
}
}
return maxSeq;
}