最长连续序列 python

### 最长连续序列算法的 Python 实现要找到一个未排序整数数组中的最长连续序列，可以通过哈希集合来优化查找过程。这种方法的时间复杂度为 \(O(n)\)，满足高效性的需求。以下是基于引用[^4]中提到的方法的具体实现： #### 使用哈希表解决问题为了快速判断某个数字是否存在以及其相邻数字的情况，可以利用哈希集合存储所有的数字。对于每一个数字，尝试扩展它的上下边界直到无法继续为止，并记录当前的最大长度。 ```python def longest_consecutive(nums): num_set = set(nums) # 将列表转换成集合以便于快速查询 max_length = 0 for num in num_set: if num - 1 not in num_set: # 只有当num是某一段序列的第一个数字时才进入循环 current_num = num current_streak = 1 while current_num + 1 in num_set: # 向右延伸尽可能远的距离 current_num += 1 current_streak += 1 max_length = max(max_length, current_streak) # 更新最大长度 return max_length ``` 上述代码的核心逻辑在于只对可能是新序列起点（即 `num-1` 不在集合中）的数字进行操作，从而避免重复工作并保持线性时间复杂度。 #### 复杂度分析 - 时间复杂度：\(O(n)\)，因为每个元素最多被访问两次——一次作为可能的新序列起始点，另一次是在向右延展过程中。 - 空间复杂度：\(O(n)\)，用于创建辅助数据结构 (set). 这种解法不仅简单易懂而且性能优越，在处理大规模随机分布的数据集上表现尤为突出。

创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考

下一篇 python桌面程序自动化