題目出處

128. Longest Consecutive Sequence

難度

medium

個人範例程式碼 – 2022/5/30 一刷，節省空間另解

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

        hashset = set(nums) # O(N)
        current_max = 0

        while(hashset):
            num = hashset.pop()

            # hashset.remove(num)
            high, low = num+1, num-1
            while high in hashset:
                hashset.remove(high)
                high += 1 # end more + 1
            while low in hashset:
                hashset.remove(low)
                low -= 1 # end more - 1

            current_max = max(current_max, high - low - 1)

        return current_max

算法說明

這邊把下方的第一版空間使用再次簡化，
我們不用 visited 了！我們打算只使用一個 hashset 搞定全部事情！

這樣就是考驗對於 set 熟悉的程度了，我們會用到：

• set.remove()：時間 O(1)
• set.pop()：任意取一個 set 的內容，並刪除，時間 O(1)

input handling

處理沒有 input 的情況，return 0

Boundary conditions

用 while(set) 來檢查 set 裡面還有沒有內容，如果沒有就搜尋完畢。
(邊搜尋的過程，一邊刪除 set 的內容)

個人範例程式碼 – 2022/5/30 一刷

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

        hashset = set(nums) # O(N)
        visited = set()
        current_max = 0

        for num in nums: # O(N)
            if num in visited: # O(1)
                continue

            cnt = 1
            visited.add(num)
            high, low = num+1, num-1
            while high in hashset:
                visited.add(high)
                high += 1
                cnt += 1
            while low in hashset:
                visited.add(low)
                low -= 1
                cnt += 1

            current_max = max(current_max, cnt)

        return current_max

算法說明

滿特別的一個題目。

直覺會想用 sort 來解，但題目要求 O(N) 時間內解完，
因此光是 sort 如果就會花上 O(NlogN) 就會時間超過。

因此我們採用「用空間來換取時間的方法」，
我們建立兩個 hashset，一個存 list 內的所有數字，一個存 visited。

每次當我們搜尋的過程中，就新增一個 visited。
因此如果像是題目要的搜尋 [100,4,200,1,3,2]

找到 4 時，會順便把 1, 2, 3 順便都找完，
而輪到 1, 2, 3 時就會跳過。

input handling

處理沒有 input 的情況，return 0

Boundary conditions

用 for 來控制範圍

Reference

• Python3 集合
• 最长连续序列 · Longest Consecutive Sequence