LeetCode128_最长连续序列
原创
wx5861be15b7630博主文章分类:python刷题 ©著作权
©著作权归作者所有:来自51CTO博客作者wx5861be15b7630的原创作品,请联系作者获取转载授权,否则将追究法律责任
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 提示:0 <= nums.length <= 105-109 <= nums[i] <= 109
2. 题解
from typing import Listclass Solution: def longestConsecutive(self, nums: List[int]) -> int: if len(nums) == 0: return 0 nums.sort() res = [] count = 1 for right in range(1, len(nums)): left = right - 1 if nums[right] - nums[left] == 0: # 判断是否相同,相同则跳过 continue elif nums[right] - nums[left] == 1: # 判断是否连续 res.append(nums[right]) count = max(len(res) + 1, count) # 随时计算最大值 else: res = [] return countif __name__ == "__main__": s = Solution() # nums = [100,4,200,1,3,2] # nums = [1,2,0,1] nums = [0] a = s.longestConsecutive(nums) print(a)
- 赞
- 收藏
- 评论
- *举报
Original: https://blog.51cto.com/u_12461028/5454132
Author: wx5861be15b7630
Title: LeetCode128_最长连续序列
原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/516664/
转载文章受原作者版权保护。转载请注明原作者出处!