最长连续序列

秒速五厘米 2022-01-20 00:59 197阅读 0赞

## 1、问题描述 ##

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

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

示例:

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

## 2、解法 ##

### 2.1 排序 ###

时间复杂度O(n log(n))

public int longestConsecutive(int[] nums) { 
    		if(nums==null || nums.length<1) { 
    			return 0;
    		}
            Arrays.sort(nums);
            int res_count=1;
            int temp_count =1;
            for(int i=1;i<nums.length; i++) { 
            	if(nums[i] == nums[i-1]+1) { 
            		res_count = Math.max(res_count, ++temp_count);
            	}else if (nums[i] != nums[i-1]) { 
            		temp_count=1;
    			}
            }
            return res_count;
        }

### 2.2 使用HashSet ###

时间复杂度O(n)

public int longestConsecutive(int[] nums) { 
    		if(nums==null || nums.length<1) { 
    			return 0;
    		}
            int res_count=1;
            int temp_count =1;
            HashSet<Integer> set = new HashSet<Integer>();
            for(int num:nums) {  
            	set.add(num);
            }
            
            for(int num:nums) { 
            	//只需要从最长连续序列的左侧端点开始即可
            	if(!set.contains(num-1)) { 
            		temp_count=1;
            		while(set.contains(++num)) { 
            			res_count = Math.max(res_count, ++temp_count);
            		}
            	}
            }
            
            return res_count;
        }

发表评论取消回复

表情：

评论列表（有 0 条评论，197人围观）

还没有评论，来说两句吧...

相关阅读

相关 674. 最长连续递增序列

> 示例 1： > > 输入：nums = \[1,3,5,4,7\] > 输出：3 > 解释：最长连续递增序列是 \[1,3,5\], 长度为3。 > 尽管 \

- 日理万妓/ 2022年10月07日 06:48/ 0 赞/ 168 阅读

相关算法题目——最长连续序列

题目链接：[leetcode.128][] ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_te

女爷i/ 2022年09月15日 12:46/ 0 赞/ 127 阅读

相关 Leetcode 128. 最长连续序列

题目重述给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

桃扇骨/ 2022年09月10日 00:29/ 0 赞/ 142 阅读

相关 674. 最长连续递增序列

给定一个未经排序的整数数组，找到最长且连续的的递增序列。示例 1: 输入: [1,3,5,4,7] 输出: 3 解释: 最长连续递增序列是 [1,

￡神魔★判官ぃ/ 2022年05月27日 10:09/ 0 赞/ 185 阅读

相关最长连续序列 LeetCode(思维)

给定一个未排序的整数数组，找出最长连续序列的长度。要求算法的时间复杂度为 O(n)。示例: 输入: [100, 4, 200, 1, 3, 2] 输出

你的名字/ 2022年05月14日 10:45/ 0 赞/ 186 阅读

相关 LeetCode 最长连续序列

> 给定一个未排序的整数数组，找出最长连续序列的长度。 > > 要求算法的时间复杂度为 O(n)。 > > 示例: > > 输入: [100, 4, 200, 1

妖狐艹你老母/ 2022年04月23日 14:42/ 0 赞/ 184 阅读

相关 LeetCode-128. 最长连续序列

[128. 最长连续序列][128.] 给定一个未排序的整数数组，找出最长连续序列的长度。要求算法的时间复杂度为 O(n)。示例: 输入: [100,

川长思鸟来/ 2022年02月20日 16:35/ 0 赞/ 214 阅读

相关最长连续序列

1、问题描述给定一个未排序的整数数组，找出最长连续序列的长度。要求算法的时间复杂度为 O(n)。示例: 输入: [100, 4, 200, 1, 3,

秒速五厘米/ 2022年01月20日 00:59/ 0 赞/ 198 阅读

相关 674-最长连续递增序列

题目描述给定一个未经排序的整数数组，找到最长且连续的的递增序列。示例 1: 输入: [1,3,5,4,7] 输出: 3 解释: 最长连

布满荆棘的人生/ 2022年01月14日 11:21/ 0 赞/ 195 阅读

相关最长上升连续子序列

给定一个整数数组（下标从 0 到 n-1， n 表示整个数组的规模），请找出该数组中的最长上升连续子序列。（最长上升连续子序列可以定义为从右到左或从左到右的序列。）注...

系统管理员/ 2021年03月28日 14:43/ 0 赞/ 551 阅读