LeetCode--128--最长连续序列(python)

给定一个未排序的整数数组，找出最长连续序列的长度。

要求算法的时间复杂度为 O(n)。

示例:

输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

暴力超时。。。

class Solution:

    def longestConsecutive(self, nums: List[int]) -> int:

        longestSequence = 0

        for num in nums:

            curNum = num

            streak = 1

            while curNum +1 in nums:

                curNum += 1

                streak += 1

            longestSequence = max(longestSequence,streak)

        return longestSequence

先排序，在有序list中，判断前一个数字是否比后一个少1，注意最后一个可能是最长连续序列的一部分，所以最后要再比一次

 class Solution:

     def longestConsecutive(self, nums: List[int]) -> int:

         if not nums:

             return 0

         nums.sort()

         longestSequence = 1

         curStreak = 1

         for i in range(1,len(nums)):

             if nums[i] != nums[i-1]:

                 if nums[i] == nums[i-1]+1:

                     curStreak += 1

                 else:

                     longestSequence = max(longestSequence,curStreak)

                     curStreak = 1

         return max(longestSequence, curStreak)

巴特西

LeetCode--128--最长连续序列(python)

最新文章

热门文章