LeetCode03：最长连续序列

3.最长连续序列

题目

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：

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

示例 2：

1
2
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

题解

（1）官方题解

哈希表

考虑枚举数组中的每个数x，考虑以其为起点，不断尝试寻找x+1,x+2…是否存在。假设匹配到了x+y，那么以x为起点的最长连续序列为x,x+1,x+2…x+y，其长度为y+1，不断枚举并更新答案即可。

对于匹配的过程，暴力匹配是O(n)遍历数组去看是否存在这个数，更高效的匹配是用一个哈希表存储数组中的数，查看一个数是否存在，优化到O(1)的时间复杂度。

仅仅是这样，算法时间复杂度最坏情况下还是会达到O($n^2$)（即外层需要枚举O(n)个数，内层需要暴力匹配O(n)次），无法满足题目的要求。但仔细分析这个过程，我们会发现其中执行了很多不必要的枚举，已知有一个x,x+1,x+2…x+y的连续序列，而重新从x+1,x+2…x+y处开始匹配，得到的结果一定不会优于枚举x为起点的答案，因此，需要跳过。

判断是否跳过：要枚举的数x一定是在数组中不存在前驱数 x-1的。

时间复杂度：外层循环需要O(n)的时间复杂度，只有当一个数是连续序列的第一个数的情况下才会进入内层循环，然后在内层循环中匹配连续序列中的数，因此数组中的每个数只会进入内层循环一次。根据上述分析可知，总时间复杂度为 O(n)。

空间复杂度：O(n)。哈希表存储数组中所有的数需要 O(n)的空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def longestConsecutive(self,nums):
        longest_streak = 0
        num_set = set(nums)
        
        for num in num_set:
            if num - 1 not in num_set:
                current_num = num
                current_streak = 1
                
                while current_num + 1 in num_set:
                    current_num += 1
                    current_streak += 1
                
                longest_streak = max(longest_streak,current_streak)
        return longest_streak

（2）我的解法

时间复杂度：
排序：首先，算法中使用了排序，其时间复杂度为 O(n log n)，其中 n 是数组 nums 的长度。这是因为大多数比较排序算法（如快速排序、归并排序等）的时间复杂度都是 O(n log n)。

遍历：排序之后，算法遍历了排序后的数组一次以计算最长连续序列的长度。这个遍历的时间复杂度是 O(n)，因为每个元素都被访问一次。

因此，算法的总体时间复杂度主要由排序这一步骤决定，即 O(n log n)。虽然遍历也涉及到数组中的所有元素，但其时间复杂度 O(n) 在排序的时间复杂度 O(n log n) 面前可以忽略不计。

空间复杂度：

算法的空间复杂度主要取决于排序算法的空间复杂度。在 Python 中，排序通常使用 Timsort 算法，其最坏情况下的空间复杂度为 O(n)。除此之外，还使用了一个列表 res 来存储每个连续序列的长度，以及几个用于记录状态的变量（如 max_len）。因此，总体空间复杂度也是 O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def longestConsecutive(self, nums):
        if nums == []:
            return 0
        if len(nums) == 1:
            return 1
        nums = sorted(nums)
        res = []
        max_len = 1
        for i,num in enumerate(nums):
            if i<len(nums)-1: 
                if nums[i+1] - num == 1:
                    max_len +=1
                elif nums[i+1] == num:
                    pass
                else:
                    res.append(max_len)
                    max_len = 1
        res.append(max_len)
        return max(res)

知识点

使用哈希表的优势

如果输入数组非常大，排序可能会成为性能瓶颈。与之相比，使用哈希表的方法虽然在理论上最坏情况下的时间复杂度也是 O(n)，但在实际应用中往往能够更高效地解决问题，尤其是当数据量大且数组中包含大量连续序列时。

集合set()方法

set()方法在Python中用于创建一个无序且不重复的元素集合。这是一种基本的数据结构，适用于去除重复元素以及执行各种集合操作（如并集、交集、差集等）。set()可以接收一个可迭代对象作为输入，比如列表、元组、字典等，然后将其转换成一个集合。如果不提供任何参数，set()会创建一个空集合。

  • 集合中的元素必须是不可变类型（如整数、浮点数、字符串、元组），不能是可变类型（如列表、字典）。
  • 使用{}可以创建集合，但如果没有提供任何元素，Python会将其解释为一个空字典而不是空集合。因此，创建空集合必须使用set()。
  • set()创建的集合是无序的，所以无法保证每次遍历集合时元素的顺序相同。