LeetCode Top Interview 150) Longest Consecutive Sequence

Question

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.

Constraints:

• 0 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:

---

---

정렬되지 않은 정수 리스트 nums가 주어지고, 연속적으로 이어지는 가장 긴 길이값을 반환하는 문제입니다. 연속적으로 이어지는 값들은 리스트 내에서 연속일 필요가 없고, 다음 값이 존재하기만 하면 됩니다. ([1,4,2,3,1,1,4] -> 연속길이 = 4)

제가 생각한 코드는 다음과 같습니다.

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        n_set = set(nums)
        max_len = 0
        
        while n_set:
            num = n_set.pop()
            num_down,num_up = num,num
            now_len = 1

            while num_down-1 in n_set:
                now_len += 1
                num_down -= 1
                n_set.remove(num_down)

            while num_up+1 in n_set:
                now_len += 1
                num_up += 1
                n_set.remove(num_up)

            max_len = max(max_len,now_len)
        return max_len

• n_set : nums의 집합 형태입니다. 중복되는 원소가 사라져도 상관이 없고 순서도 중요하지 않기에 집합형태로 바꿔줍니다. 집합에 원소를 추가하는데 O(1)의 시간복잡도를 가지므로 이 때의 시간복잡도는 O(n)입니다.
• max_len : 최대 길이를 저장하는 변수입니다.
• n_set이 공집합이 되기 전까지 다음 과정을 진행합니다.
  • 무작위로 원소 값을 하나 가져옵니다.
  • 이 값의 위, 아래의 값들을 하나씩 제거하며 길이값now_len을 업데이트합니다.
  • 저장된 최대길이max_len과 비교해서 큰 값을 max_len에 저장합니다.
  • 이 때 원소를 찾고, 제거될 때 O(1)의 시간복잡도를 가지므로 모든 원소를 찾고 제거되기까지 시간복잡도는 O(2 * n)입니다.
• max_len을 반환합니다.

---

집합이 해시테이블의 구조를 가지기에 탐색하는데 O(1)의 시간복잡도를 가진다는 점을 이용하였습니다.
최종적으로 O(3 * n)의 복잡도로 문제를 해결할 수 있었고 알고리즘 자체는 단순했습니다.

가장 처음에는 heap구조를 만들어 heappop을 이용해보는 방법이 생각나서 구현했지만 시간복잡도가 O(n)이라는 걸 나중에 봐서.. O(nlogn)의 시간복잡도를 가지는 heap 사용방법은 두고 새로 풀었습니다.
우선 답까진 나왔고 런타임Beats도 60%대가 나왔기에 시간초과로 두지는 않은 듯 합니다.
힙 코드는 다음과 같았습니다.

from heapq import heapify,heappop

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if not nums:
            return 0
        heapify(nums)
        last_num = heappop(nums)
        now_len,max_len = 1,1

        while nums:
            now_num = heappop(nums)

            if now_num - last_num == 1:
                now_len += 1
            elif now_num - last_num == 0:
                continue
            else:
                max_len = max(max_len,now_len)
                now_len = 1

            last_num = now_num

        return max(max_len,now_len)

아래의 첫 번째는 힙 코드의 결과이고 두 번째가 집합 코드 결과입니다. 아무래도 힙 코드는 변수 저장이 필요한게 거의 없어서 메모리 사용량이 좋게 나온듯 합니다.

• 힙 코드
  

• 집합 코드