128.最长连续序列

给定一个未排序的整数数组 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\le nums.length\le {10}^5$
• ${-10}^9\le nums[i]\le {10}^9$

解法一(排序)

思路分析:

1. 题目要求:找出数字连续的最长序列,且不需要在原数组中连续,则可以尝试对原数组进行排序;
2. 排序之后,在遍历数组,判断 相邻元素是否连续, 若连续则计数长度+1, 若不连续则将计数长度归1,重新开始计数;
3. 因为序列长度,需要算上第一个元素,即 只有一个元素时, 序列长度为1, 所以初始序列长度为 1;
4. 同时需要注意: 题目并未说明数组中的元素不重复, 所以需要排除重复元素的情况

实现代码如下:

class Solution {
    public int longestConsecutive(int[] nums) {
		int n = nums.length;
		if (n == 0) {
			return 0;
		}
		// 排序
		Arrays.sort(nums);
		// 最小连续序列长度为 1
		int max = 1;
		int flag = 1;
		for (int i = 0; i < n-1; ++ i) {
			if (nums[i] == nums[i+1] - 1) {
				// 若连续 则长度增加
				flag ++;
			} else if (nums[i] == nums[i+1]) {
				// 排除连续相等的元素
				continue;
			}else {
				// 不连续 则重新计数
				flag = 1;
			}
			// 时刻更新最长序列
			max = Math.max(flag, max);
		}
		return max;
    }
}

提交结果如下:

解答成功:

执行耗时:12 ms,击败了98.27% 的Java用户

内存消耗:55.3 MB,击败了95.98% 的Java用户

复杂度分析:

• 时间复杂度: $O(n\times logn)$, 对数组排序的复杂度;
• 空间复杂度: $O(1)$

解法二(哈希表)

思路分析:

1. 对数组中的每个数进行枚举, 然后再在数组中寻找x+1, x+2, x+3, ..., 当匹配到x+y,即此时序列长度为y+1
2. 但是每次遍历匹配的时间复杂度为$O(n)$,涉及到匹配的优化可以考虑使用哈希表来减少匹配的复杂度;即查看一个数是否存在的时间复杂度可以优化为$O(1)$
3. 所以只需要遍历数组元素,然后以每个元素为起点x,持续判断x+?是否存在,即可得到以x为起点的序列长度;
4. 但是此时的时间复杂度依然为 $O(n^2)$,每个元素可能会重复遍历多次, 比如序列[100,4,200,1,3,2]中,以2为起点和以1为起点都会导致重复遍历;
5. 最优情况是: 只从每个序列的起点开始遍历获取序列长度,例如序列[100],序列长度为1,起点为100, 序列[1,2,3,4],只从起点1遍历一次,而不会再去从2开始遍历[2,3,4];
6. 所以可以在遍历数组元素时,判断当前元素是否为序列的起点,若为序列起点,则开始匹配序列,并获取序列长度,若不是序列起点,则跳过;
7. 判断一个元素x是否为序列起点, 可以判断哈希表中是否存在元素x-1,若存在,则说明序列可以从x-1开始,即x不是序列起点; 若不存在,则说明x为序列起点
8. 同时,需要考虑数组元素的重复情况,以及哈希表的选取,因为不需要绑定数组元素的索引,即不需要使用Map来作为哈希表; 即使用Set作为哈希表即可,同时可以起到去重的作用;

实现代码如下:

class Solution {
	public int longestConsecutive(int[] nums) {
		// 定义哈希表
		Set<Integer> set = new HashSet<>();
		// 遍历数组 并存入哈希表中去重
		for (int num : nums) {
			set.add(num);
		}
		// 最长序列长度
		int maxLen = 0;
		for (Integer num : set) {
			// 判断当前元素是否为序列起点
			if (!set.contains(num-1)) {
				// 为序列起点 遍历序列获取长度
				// 当前元素
				int currentNum = num;
				// 当前序列长度
				int currentLen = 1;
				while (set.contains(currentNum + 1)) {
					// 序列长度增加
					++ currentLen;
					++ currentNum;
				}
				maxLen = Math.max(maxLen, currentLen);
			}
		}
		return maxLen;
	}
}

提交结果如下:

解答成功: 执行耗时:27 ms,击败了59.27% 的Java用户 内存消耗:66.1 MB,击败了6.98% 的Java用户

复杂度分析:

• 时间复杂度:$O(n)$,只需$O(n)$的遍历数组元素;
• 空间复杂度:$O(n)$,需要使用哈希表来存储数组元素;