阅读量:1
题目
给定一个未排序的整数数组 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
排序法
排序法在最坏情况下的时间复杂度为O(nlogn)，不满足本题时间复杂度为O(n)的要求。但它提供了一个不同的解题视角，还是值得我们学习一下的。使用排序法求解本题的主要步骤如下。
1、首先，将输入数组nums进行排序。这一步的目的是使得连续的数字相邻，便于后续遍历查找连续序列。
2、对排序后的数组进行遍历，并初始化两个变量。其中，current_streak用于记录当前连续序列的长度，longest_streak用于记录遇到的最长连续序列的长度。
3、在遍历过程中，比较当前元素与前一个元素的关系。如果当前元素正好比前一个元素大1，则说明它们属于同一个连续序列，此时current_streak加1。否则，说明遇到了新的序列起点，此时更新longest_streak（如果current_streak大于longest_streak），并将current_streak重置为1。
注意：需要对数组中存在相同元素的情况进行额外处理，以避免重复元素导致的误判。
根据上面的算法步骤，我们可以得出下面的示例代码。
def get_longest_consecutive_by_sort(nums): if not nums: return 0 nums.sort() longest_streak = 1 current_streak = 1 for i in range(1, len(nums)): # 避免重复元素导致的误判 if nums[i] != nums[i-1]: if nums[i] == nums[i-1] + 1: current_streak += 1 else: longest_streak = max(longest_streak, current_streak) current_streak = 1 return max(longest_streak, current_streak) print(get_longest_consecutive_by_sort([100, 4, 200, 1, 3, 2])) print(get_longest_consecutive_by_sort([0, 3, 7, 2, 5, 8, 4, 6, 0, 1]))哈希法
使用哈希法的基本思想如下：首先，将所有数组中的元素添加到哈希集合中，以便快速查询一个数字是否已存在。然后，遍历数组中的每个元素，对于每个元素，检查它是否是某个连续序列的起始点（即检查num - 1不在哈希集合中）。如果是起始点，则尝试向后扩展序列，同时更新最长序列长度。为了避免重复计算，每当我们确定了一个数字属于某个连续序列时，就将其从哈希集合中移除。使用哈希法求解本题的主要步骤如下。
1、初始化。创建一个空的哈希集合num_set，用来存储数组中的所有数字。
2、填充哈希集合。遍历数组nums，将所有元素添加到哈希集合num_set中。
3、遍历并检查连续性。再次遍历数组nums，对于每个元素，检查它是否能作为连续序列的起点，即检查 num - 1 是否不在 num_set 中。
4、扩展序列并更新长度。如果找到了一个起点，就尝试通过不断检查 num + 1 是否在 num_set 中来扩展序列，并相应地更新最长序列长度。
5、移除已访问元素。在扩展序列的过程中，将访问过的数字从 num_set 中移除，以避免之后的重复计算。
6、返回找到的最长连续序列的长度。
根据上面的算法步骤，我们可以得出下面的示例代码。
def get_longest_consecutive_by_hash(nums): if not nums: return 0 num_set = set(nums) longest_streak = 0 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 print(get_longest_consecutive_by_hash([100, 4, 200, 1, 3, 2])) print(get_longest_consecutive_by_hash([0, 3, 7, 2, 5, 8, 4, 6, 0, 1]))总结
使用哈希法求解本题时，每个元素仅被访问两次：一次加入哈希集合，另一次作为序列起点检查。遍历和序列扩展操作均在常数时间内完成，故总的时间复杂度为O(n)，满足本题的要求。另外，哈希法需要额外的空间来存储哈希集合。最坏情况下，数组中的所有元素都是唯一的，因此哈希集合将存储n个元素，空间复杂度为O(n)。
