[leetcode] 128. Longest Consecutive Sequence

문제 설명

링크
O(n) 의 시간복잡도로 정렬되어있지 않은 배열에서 연속된 숫자들의 최대 길이를 찾는 문제

접근 - SET

• 파이썬의 set
  • add O(1)
  • pop O(1)
  • remove O(1)
  • in O(1)
• 배열을 set으로 변환 후, in 키워드를 통해 찾기

코드 1

• 리트코드 solution

    def longestConsecutive(self, nums: [int]) -> int:
        longest_streak = 0
        num_set = set(nums)

        for num in num_set:
            if num - 1 not in num_set:
                current_num = num
                current_streak = 1

                while current_num + 1 in num_set:
                    current_num += 1
                    current_streak += 1

                longest_streak = max(longest_streak, current_streak)

        return longest_streak

코드 2

• 변형

    def longestConsecutive(self, nums: [int]) -> int:
        nums = set(nums)
        res = 0
        while nums:
            n = nums.pop()
            m = n - 1
            o = n + 1
            while m in nums:
                nums.remove(m)
                m -= 1
            while o in nums:
                nums.remove(o)
                o += 1
            res = max(res, o - m - 1)
        return res