題目解釋
給定一個 unsorted 的整數陣列 nums
,傳回最長連續序列的長度。
演算法的 time comlexity 必須是 O(n)。
範例
- 輸入:
nums = [100, 4, 200, 1, 3, 2]
- 輸出:
4
輸出 4
是因為 1, 2, 3, 4
是最大的連續序列。
最佳解法
首先,我們可以思考「連續」的定義:
當有一個數字 n
時,只要再給一個 n - 1
的數值,我們就可以拿到一個連續的 seq,例如 [0, 1] 等。
=>因此,如果 n - 1
存在於 array 中的話,就代表 n
不是連續 seq 的起點!
所以我們需要將 traverse 的結果寫在某種資料結構內,而這個最理想的資料結構就是 set
。
步驟
- 將
nums
直接轉換為set
- 確保我們在連續 seq 的起點 (
if (n - 1) not in nums_set
) - 從起點持續向後滾動並累積
seq_len
- 最後 return
max_seq_len
⚠️ 注意
- Q:為什麼
max_seq_len = max(seq_len, max_seq_len)
這段不可以放在while
裡? - A:因為如果我們沒有進到
while
迴圈那max_seq_len
就不會被更新,例如nums = [0]
時,我們期待的結果是1
,但是因為寫在裡面所以會回傳錯誤的0
。
程式碼
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
nums_set = set(nums)
max_seq_len = 0
for n in nums_set:
if (n - 1) not in nums_set:
seq_len = 1
while (n + seq_len) in nums_set:
seq_len += 1
max_seq_len = max(seq_len, max_seq_len)
return max_seq_len
時間複雜度
O(n)
,n 是 nums
的元素個數。
空間複雜度
O(n)
。
結語
看起來很簡單,但若沒想清楚的下場就是一直吃 Wrong Answer 🥲。
Latest posts by 數據女巫 𝔻.𝕡𝕪𝕤 🔮 (see all)
- [推薦工具] 讓程式碼截圖變的美美的吧!VScode CodeSnap 與 3 種同功能線上工具介紹 - 2025-01-05
- [AI 繪圖初級教學] 用 X/Y/Z Plot 比較 Stable Diffusion 的 prompt 與 LoRA 效果 - 2024-12-27
- [AI 繪圖中級篇教學] Stable Diffusion WebUI WD14 Tagger 介紹 - 2024-12-26