[LeetCode] 128. Longest Consecutive Sequence

- Problem

128. Longest Consecutive Sequence

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 <= 10^5
• -10^9 <= nums[i] <= 10^9

배열에서 연속적으로 1씩 증가하는 수의 최대 길이를 찾는 문제이다. (?)
주어진 예제를 보면 문제를 이해하기 쉽다.

- 내 풀이

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if not nums:
            return 0
        
        nums = sorted(set(nums))
        answer = 0
        cnt = 1
        
        for i in range(1, len(nums)):
            if nums[i] == nums[i-1] + 1:
                cnt += 1
            else:
                answer = max(answer, cnt)
                cnt = 1
                
            
        return max(answer, cnt)

- 결과

O(n)을 만족하는 풀이를 떠올리다가 우선 생각나는 방식대로 풀었다.
주어진 nums에는 중복 원소가 있기에 set으로 바꾼 후, 다시 sort를 해준다. O(n) + O(nlogn)
정렬된 배열을 돌면서 가장 긴 연속적으로 증가하는 부분 배열을 찾는다. O(n)
결과적으로, 시간 복잡도 O(nlogn)을 가지는 풀이일뿐더러, 누구나 굉장히 쉽게 떠올릴 수 있는 풀이방법이다.

- 다른 사람 풀이 (set)

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        answer = 0 
        nums = set(nums)
        
        for num in nums:
            if num - 1 not in nums:
                y = num
                cnt = 0
                while y in nums:
                    y += 1
                    cnt += 1
                answer = max(answer, cnt)
        
        return answer
                    

leetcode 셀럽 StefanPochmann님의 코드이다.

우선, in, not in 연산을 O(1)로 하기 위해 주어진 배열을 set으로 바꾼다.
for문 안의 while문으로 인해 O(n^2)처럼 보이지만, if num - 1 not in nums이 한 줄이O(n)을 만족한다.

격공.

- 결과

...