LeetCode 솔루션

[7/5] 128. Longest Consecutive Sequence

mingki 쪽지보내기 메일보내기 자기소개 아이디로 검색 전체게시물 작성
작성일 2022.07.05 20:14

6,639 조회
1 댓글
0 추천
0 비추천
목록 게시글 쓰기

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

#Amazon, #Google, #Microsoft, #Facebook, #Spotify, #Apple, #Bloomberg, #Adobe, #Qualtrics, #Morgan Stanley, #Array, #Hash Table, #Union Find

링크

https://leetcode.com/problemset/all/ 12522 회 연결

익명
작성일 2022.07.06 10:08

# 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

[code=Python 3]# 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[/code]