参考资料:
考点:哈希 & [题干]
Input: nums = [100,4,200,1,3,2] Output: 4 Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
做的时候冥思苦想了半天,因为这个题目要求是O(n)的解法,后来看到题解的时候还一度怀疑官方解法达不到O(n)。
1. 心路历程
首先,列表中可能有重复元素,但在结果里是不会显示出来的,因此首先把nums列表转换成set这个没问题。然后,需要寻找最长序列,不遍历一遍是肯定达不到的。但是题干也给了提示O(n),也就是说基本上让你遍历一遍就把结果找到,这就很难了。。
比如一个列表[3, 1, 2, 4],我们遍历到 3 的时候,需要判断它前面一个整数2和后面一个整数4是否同样在列表中,这个判断的时间可以在O(1)中完成吗?我想破头也没想出来,但实际上,使用集合的in操作是可以实现的。这里可以参考这个文章:https://www.jianshu.com/p/a8fa3d31aa40,里面列举了常见数据结构基本操作的时间复杂度。而集合的in操作就是O(1)的,因为内部使用了hash表。值得注意的是,这篇文章同样提到了set的内部实现是dict,因此dict的查找也是O(1),看来dict的功能比集合要强一些呀~ 其实,想到使用集合in操作这个判据,后面的就水到渠成了,对于上面这个例子,如果当前遍历到3,首先查看3 - 1 = 2在集合里,则直接跳过,只有当遍历到1的时候,发现0没有在集合里,就向后遍历,一直发现 1 2 3 4都在,则最大长度是4。写出的代码如下:
class Solution(object): def longestConsecutive(self, nums): """ :type nums: List[int] :rtype: int """ num_set = set(nums) max_len = 0 for num in num_set: if num - 1 not in num_set: current_len = 1 current_num = num while current_num + 1 in num_set: current_len += 1 current_num = current_num + 1 max_len = max(max_len, current_len) return max_len标签:set,Sequence,nums,len,current,Hot,num,Longest,遍历 From: https://www.cnblogs.com/chester-cs/p/17469510.html