本文主要是介绍【hot100篇-python刷题记录】【最长连续序列】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
R7-哈希篇
思路:sort一下先
然后使用双指针遍历计数,同时从数组头开始。
按照题目的意思,相同元素只能取一个,所以可以用set
class Solution:def longestConsecutive(self, nums: List[int]) -> int:if len(nums)<=1:return len(nums)nums.sort()nums1=set(nums)n=len(nums1)mx=1for i in nums1:if i-1 not in nums1:cur=imx1=1while cur+1 in nums1:mx1+=1cur+=1mx=max(mx,mx1)return mx
和之前的解法不一样
class Solution:def longestConsecutive(self, nums: List[int]) -> int:#相同元素没有意义,可以舍弃nums=set(nums)ans=0#并查集#值为离散的,使用字典#准备用做parent字典fa={num:num for num in nums}#对于每个数字来说,以它开始的最长连续初始都为1size={num:1 for num in nums}def find(x):if fa[x]!=x:fa[x]=find(fa[x])return fa[x]def union(f,to):f=find(f)to=find(to)if f!=to:fa[f]=tosize[to]+=size[f]#遍历数组,满足union时,取maxfor num in nums:if num+1 in fa:union(num,num+1)#size.values()当size是字典是能取所有的值出来if size:ans=max(size.values())return ans
还优化了
这篇关于【hot100篇-python刷题记录】【最长连续序列】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!