手机端网站建设,wordpress工作室,做自己的免费网站,公司装修风格给定一个未排序的整数数组 nums #xff0c;找出数字连续的最长序列#xff08;不要求序列元素在原数组中连续#xff09;的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。 示例 1#xff1a;
输入#xff1a;nums [100,4,200,1,3,2]
输出#xff1a;4
解…给定一个未排序的整数数组 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 方法一HashSet【时间复杂度O(n)】
优化
1.直接遍历查找改为哈希表查找时间复杂度为O(1)
2.对一个连续序列中的元素进行删减让其只在最小的元素才开始1遍历避免重复遍历
代码
class Solution { //方法一HashSet public int longestConsecutive(int[] nums) { // 建立一个存储所有数的哈希表同时起到去重功能 SetInteger hashset new HashSet(); for(int num : nums){ hashset.add(num); } int ans 0; // 存储最长连续序列的长度 // 遍历去重后的所有数字 for(int num : hashset){ int cur num; // 只有当num-1不存在时才开始向后遍历num1num2num3...... if(!hashset.contains(cur - 1)){ while(hashset.contains(cur 1)){ cur; } } ans Math.max(ans, cur - num 1); } return ans; }
}
