江西建设单位网站,做网站标志过程,广州做手机网站建设,做外贸c2c网站有哪些欢迎收藏Star我的Machine Learning Blog:https://github.com/purepisces/Wenqing-Machine_Learning_Blog。如果收藏star, 有问题可以随时与我交流, 谢谢大家#xff01;
链接:
128_最长连续序列
直觉
输入: nums [100, 4, 200, 1, 3, 2]输出: 4解释: 最长的连续元素序列是…欢迎收藏Star我的Machine Learning Blog:https://github.com/purepisces/Wenqing-Machine_Learning_Blog。如果收藏star, 有问题可以随时与我交流, 谢谢大家
链接:
128_最长连续序列
直觉
输入: nums [100, 4, 200, 1, 3, 2]输出: 4解释: 最长的连续元素序列是 [1, 2, 3, 4]。因此它的长度是 4。
首先我们需要找到每个递增序列的起始位置并且舍弃重复的值。所以先使用 set(nums) 将 nums 转换为一个集合。集合中的每个值可能是起始位置也可能只是序列的一部分。我们只需要找到起始值。
考虑列表 [1, 2, 3, 4, 5, 6]。如果不只找起始点它会计算从 1-62-63-6 等开始的序列导致 ( O ( n 2 ) (O(n^2) (O(n2) 的复杂度。为了确保线性时间复杂度我们需要仅识别每个间隔的起始点。
当遇到一个值时如果 n-1 在集合中跳过它因为它不是起始位置。如果 n-1 不在集合中说明 n 是一个起始值我们将长度初始化为 1。当 n length 在集合中时长度加 1。然后将结果更新为 length 和当前结果中的最大值。
方法
我们将找到每个起始位置并使用哈希集合存储 nums 的所有值。当我们找到一个起始位置时我们将从这个位置计算序列的长度。然后更新最终结果并返回它。
找到起始位置:
如果 n-1 不在 numset 中那么 n 是一个起始位置。将长度初始化为 1。当 n length 在 numset 中时我们增加长度。最后用找到的最长长度更新结果。
复杂度 时间复杂度: O ( n ) O(n) O(n) 创建集合: O ( n ) O(n) O(n)遍历列表: O ( n ) O(n) O(n)检查序列的起始点并计算长度: O ( n ) O(n) O(n) 空间复杂度: O ( n ) O(n) O(n) 集合的空间: O ( n ) O(n) O(n)其他变量的空间: O ( 1 ) O(1) O(1)
代码
class Solution(object):def longestConsecutive(self, nums)::type nums: List[int]:rtype: intnumset set(nums)longest 0for n in nums:# calculate just from the starting positionif n-1 not in numset:length 1while n length in numset:length1longest max(longest, length)return longest
