算法11.数组的最长连续序列

叶子创业记

共 690字,需浏览 2分钟

 ·

2021-10-28 08:32

题目:

    给定一个未排序的整数数组,找出最长连续序列的长度。

    要求算法的时间复杂度为 O(n)。


示例:

    输入: [100, 4, 200, 1, 3, 2]

    输出: 4

    解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。




解题思路:

    当前数字的最大连续序列长度一定是它前一个数字的长度+?后一个数的长度,再加上1。然后我们使用一个hash表来记录每个数字遍历过程中的最大序列长度。



6f6389889257dcd2e348c02d2470ce3f.webp




代码如下:

/** * @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; }}


浏览 35
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报