Longest Consecutive Sequence

https://leetcode.com/problems/longest-consecutive-sequence/

Longest Consecutive Sequence - LeetCode

간단한 문제이기만

 

해시 테이블을 활용해서 푸느냐, 아니냐에 따라서 시간 복잡도가 차이난다.

 

처음에 작성한 코드

class Solution:
    def longestConsecutive(self, nums):
        if len(nums) == 0:
            return 0
        ans = 1
        nums_set = set()
        for num in nums:
            nums_set.add(num)
        nums = list(nums_set)
        nums.sort()
        result = list()
        for i in range(1, len(nums)):
            if nums[i - 1] + 1 == nums[i]:
                ans += 1
            else:
                result.append(ans)
                ans = 1
        if ans >= 1:
            result.append(ans)
        result.sort()
        return result[-1]

 

해시 테이블을 활용한 코드

class Solution:
    def longestConsecutive(self, nums):
        if len(nums) == 0:
            return 0

        nums_dict = {}
        for num in nums:
            nums_dict[num] = 0

        ans = 0
        for num in nums_dict:
            cnt = 0
            if num - 1 not in nums_dict:
                find_num = num
                while True:
                    find_num = find_num + 1
                    if find_num in nums_dict:
                        cnt += 1
                    else:
                        break
                if cnt > 0:
                    ans = max(cnt, ans)
        return ans + 1