題目出處
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 來控制範圍