LeetCode128_最长连续序列

LeetCode128_最长连续序列

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)

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。