网站 虚拟目录,软件工程师证书有用吗,小白自己做网站,WordPress 更改H标签#xff08;一#xff09;问题描述
128. 最长连续序列 - 力扣#xff08;LeetCode#xff09;128. 最长连续序列 - 给定一个未排序的整数数组 nums #xff0c;找出数字连续的最长序列#xff08;不要求序列元素在原数组中连续#xff09;的长度。请你设计并实现时间复…一问题描述
128. 最长连续序列 - 力扣LeetCode128. 最长连续序列 - 给定一个未排序的整数数组 nums 找出数字连续的最长序列不要求序列元素在原数组中连续的长度。请你设计并实现时间复杂度为 O(n) 的算法解决此问题。 示例 1输入nums [100,4,200,1,3,2]输出4解释最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。示例 2输入nums [0,3,7,2,5,8,4,6,0,1]输出9 提示 * 0 nums.length 105 * -109 nums[i] 109https://leetcode.cn/problems/longest-consecutive-sequence/description/?envTypestudy-plan-v2envIdtop-100-liked给定一个未排序的整数数组 nums 找出数字连续的最长序列不要求序列元素在原数组中连续的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1
输入nums [100,4,200,1,3,2]
输出4
解释最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2
输入nums [0,3,7,2,5,8,4,6,0,1]
输出9
提示
0 nums.length 105-109 nums[i] 109 二解决思路
这道题目要求找连续序列同时不要求序列位置连续即查找数值大小上连续的元素有几个。那么使用哈希结构中的集合Set是最合适的可以去除数组中重复的元素又能快速找到符合条件的元素。
思路很简单
找到序列的起始元素即序列当中数值最小的元素不断找到该序列中的下一个元素比当前元素大一每找到一个序列长度就加一一个数组里可能包含多个序列比较得到的多个长度取最大就是当前数组中的最大连续序列长度。
class Solution {public int longestConsecutive(int[] nums) {//将给定数组转换为集合SetInteger snew HashSet();for(int n : nums){s.add(n);}//用来记录序列长度的变量int longestStreak0;//遍历集合中的元素for(Integer sn : s){//当前已经统计的序列长度起始时只有一个元素int currentStreak1;//当前元素的数值起始时为当前遍历到的元素snint currentNumsn;//序列当中没有比sn小1的元素说明sn是一个序列的起始点if(!s.contains(sn-1)){ //只要有比sn大一的元素就说明序列还没有结束不断找序列中的下一个元素同时序列长度加一while(s.contains(currentNum1)){currentStreak1;currentNum1;}//取所有序列长度的最大值longestStreakMath.max(longestStreak,currentStreak);}}return longestStreak;}
} 三易错点 这道题要求时间复杂度为On那么就不能有排序只要针对数组排序时间复杂度就会大于On。所以这道题解题的关键是想到找序列的起点以及怎么找序列的节点。如果不找序列的起点是没有办法按顺序累加元素的。 另外也不是循环嵌套时间复杂度就一定大于O(n)的哈。像这道题里面第二层循环的执行是有条件的时间复杂度还是O(n)。
