算法11.数组的最长连续序列
叶子创业记
共 690字,需浏览 2分钟
·
2021-10-28 08:32
题目:
给定一个未排序的整数数组,找出最长连续序列的长度。
要求算法的时间复杂度为 O(n)。
示例:
输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
解题思路:
当前数字的最大连续序列长度一定是它前一个数字的长度+?后一个数的长度,再加上1。然后我们使用一个hash表来记录每个数字遍历过程中的最大序列长度。
代码如下:
/**
* @author Ted
* @version 1.0
* @date 2021/10/26 11:03
*/
public class MaxLengthSequence {
public static void main(String[] args) {
int[] nums = new int[]{100,4,200,1,3,2,5};
int i = longestSequence(nums);
System.out.println(i);
}
/**
* 最长连续序列
* @param nums
* @return
*/
private static int longestSequence(int[] nums){
int maxLen = 0;
HashMap<Integer,Integer> map = new HashMap<>();
for(int i=0;i
if(map.get(nums[i])==null) {
map.put(nums[i],1);
int left = 0,right = 0;
if(map.containsKey(nums[i]-1)) {
left = map.get(nums[i]-1);
}
if(map.containsKey(nums[i]+1)) {
right = map.get(nums[i]+1);
}
int curLen = left+right+1;
maxLen = Math.max(maxLen, curLen);
map.put(nums[i],maxLen);
//直接算出需要更新的两端位置
if(map.containsKey(nums[i]-left)){
map.put(nums[i]-left, curLen);
}
if (map.containsKey(nums[i]+right)){
map.put(nums[i]+right,curLen);
}
}
}
return maxLen;
}
}
评论