LeetCode 솔루션 분류

[7/5] 128. Longest Consecutive Sequence

컨텐츠 정보

본문

Medium
11658500Add to ListShare

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

 

Example 1:

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.

Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

 

Constraints:

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109

관련자료

댓글 1

학부유학생님의 댓글

  • 익명
  • 작성일
# O(n) Solution
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        nums = set(nums)
        
        max_len = 0
        
        while nums:
            inc = dec = nums.pop()
            
            while inc + 1 in nums:
                inc += 1
                nums.remove(inc)
            while dec - 1 in nums:
                dec -= 1
                nums.remove(dec)
            
            max_len = max(max_len, inc - dec + 1)
        
        return max_len

# O(nlogn) solution
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        
        nums = sorted(list(set(nums)))
        
        consequtive_num = 1
        max_consequtive_num = 1        
        for i in range(1, len(nums)):
            if (nums[i] == nums[i-1] + 1):
                consequtive_num += 1
            else:
                consequtive_num = 1
            max_consequtive_num = max(max_consequtive_num, consequtive_num)
                
        return 0 if len(nums)==0 else max_consequtive_num
LeetCode 솔루션 357 / 10 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


  • 현재 접속자 800 명
  • 오늘 방문자 3,069 명
  • 어제 방문자 6,975 명
  • 최대 방문자 14,831 명
  • 전체 회원수 1,536 명
알림 0