上海市建设小学网站,深圳网上专业推广公司,网站制作文章标签,公司官网搭建方案优质博文#xff1a;IT-BLOG-CN
一、题目
给定一个未排序的整数数组nums#xff0c;找出数字连续的最长序列#xff08;不要求序列元素在原数组中连续#xff09;的长度。请你设计并实现时间复杂度为O(n)的算法解决此问题。
示例 1#xff1a; 输入#xff1a;nums […优质博文IT-BLOG-CN
一、题目
给定一个未排序的整数数组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 二、代码
【1】我们首先先当的是非O(n)的方法对nums进行排序后判断最长连续序列。
class Solution {public int longestConsecutive(int[] nums) {// 我们首先想到的就是非O(N)的时间复杂度先排序在去重。if (nums null || nums.length 0) {return 0;}Arrays.sort(nums);SetInteger set new LinkedHashSet();for (int i 0; i nums.length; i) {set.add(nums[i]);}int maxLen 1;int count 1;int pre Integer.MIN_VALUE;for (int num : set) {if (num - pre 1) {count;} else {count 1;}pre num;maxLen Math.max(maxLen, count);}return maxLen;}
}【2】上面的方法不是O(n)时间复杂度所以我们需要将排序和去重这个动作的O(nlogn)的复杂度降下来可以通过哈希表存储数组中的数这样查一个数是否存在就可以优化至O(1)的时间复杂度仅仅是这样我们的算法时间复杂度最坏情况下还是会达到O(n2)即外层需要枚举O(n)个数内层需要暴力匹配O(n)次无法满足题目的要求。但仔细分析这个过程我们会发现其中执行了很多不必要的枚举如果已知有一个x,x1,x2,⋯ ,xy的连续序列而我们却重新从x1x2或者是xy处开始尝试匹配那么得到的结果肯定不会优于枚举x为起点的答案因此我们在外层循环的时候碰到这种情况跳过即可。
增加了判断跳过的逻辑之后时间复杂度是多少呢外层循环需要O(n)的时间复杂度只有当一个数是连续序列的第一个数的情况下才会进入内层循环然后在内层循环中匹配连续序列中的数因此数组中的每个数只会进入内层循环一次。根据上述分析可知总时间复杂度为O(n)符合题目要求。
class Solution {public int longestConsecutive(int[] nums) {// 我们首先想到的就是非O(N)的时间复杂度先排序在去重。if (nums null || nums.length 0) {return 0;}SetInteger num_set new HashSet();for (int i 0; i nums.length; i) {num_set.add(nums[i]);}int maxLen 0;for (int num : num_set) {// 先判断是否存在上一个数字减少时间复杂度if (!num_set.contains(num - 1)){int count 1;int currentNum num;while (num_set.contains(currentNum 1)) {currentNum 1;count 1;}maxLen Math.max(maxLen, count);}}return maxLen;}
}时间复杂度 O(n)其中n为数组的长度。具体分析已在上面正文中给出。 空间复杂度 O(n)。哈希表存储数组中所有的数需要O(n)的空间。
