当前位置：网站首页>Longest continuous sequence

Longest continuous sequence

2022-06-28 15:07:00 【Hua Weiyun】

title: The longest continuous sequence
date: 2022-04-22 11:33:47
tags: Make a little progress every day

subject

subject ： The longest continuous sequence

difficulty ： secondary

Given an array of unsorted integers nums , Find the longest sequence of consecutive numbers （ Sequence elements are not required to be contiguous in the original array ） The length of . Please design and implement it with a time complexity of O(n) The algorithm to solve this problem .

Example 1：
Input ：nums = [100,4,200,1,3,2]
Output ：4
explain ： The longest consecutive sequence of numbers is [1, 2, 3, 4]. Its length is 4.
Example 2：
Input ：nums = [0,3,7,2,5,8,4,6,0,1]
Output ：9
Tips ：0 <= nums.length <= 105
-109 <= nums[i] <= 109

Answer key ： First in the next order , One dimension dp Array ,dp[n] Record length , Finally, find the maximum dp It's worth it , The array length is 0 Just deal with it first , Note that the default value of the return value is 1, First give dp Arrays are initialized to 1, Because the smallest continuous length must contain itself, that is 1

Code ：

class Solution {    public int longestConsecutive(int[] nums) {        if(nums.length==0){            return 0;        }        // Sort below         Arrays.sort(nums);        //max Initialize to 1, Because the minimum continuous sequence length is 1, Avoid the case where there is only one element in the array , You can also write on it if Filtering ahead of time         int max = 1;        int[] dp = new int[nums.length];        // First fill in an initial length , Including itself , That is to say 1        Arrays.fill(dp,1);        for(int i=1;i<nums.length;i++){            // Bigger than the previous one , So it's continuous             if(nums[i]==nums[i-1]+1){                dp[i] = dp[i-1] + 1;            }            // Equal to the previous one , Just keep the continuous length             if(nums[i]==nums[i-1]){                dp[i] = dp[i-1];            }            max = Math.max(max,dp[i]);        }        return max;    }}