3 min read leetcode

128. Longest Consecutive Sequence

128. Longest Consecutive Sequence
Photo by Markus Spiske / Unsplash

題目描述

給定一個未排序的整數陣列 nums，找出其中最長的連續序列（例如 [5, 6, 7, 8]）。要求演算法的時間複雜度為 O(n)。

限制條件

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

測試用例思考

  • 空陣列：[] ⇒ 0
  • 無連續序列：[1, 3, 5, 7, 9] ⇒ 1
  • 重複數字：[1, 1, 1, 1, 1, 1, 1] ⇒ 1
  • 無序的連續序列：[1, 4, 3, 2, 5] ⇒ 5

解題思路

  1. 排序法：
    • 將陣列排序後，遍歷一次計算最長的連續序列長度。
    • 缺點：排序的時間複雜度為 O(n log n)，不符合題目要求的 O(n)。
  2. 並查集（Union Find）：
    • 將數字視為節點，若數字 a 和 a+1 或 a-1 存在，則合併到同一個集合。
    • 缺點：需要額外的資料結構管理，且時間複雜度較高，約為 O(n log n)。
  3. 雜湊集合（HashSet）法：
    • 將所有數字存入一個 unordered_set，以方便 O(1) 時間複雜度的查詢。
    • 遍歷每個數字，對於每個可能是序列起點的數字，嘗試找到連續序列的長度。
    • 優化點：在原始的程式碼中，對每個數字都嘗試向上下擴展，並且在過程中刪除集合中的元素。這樣會導致重複訪問數字，可以進一步優化。

優化後的解法

  • 步驟 1：將所有數字存入一個 unordered_set，自動去除重複元素。
  • 步驟 2：遍歷集合 num_set 中的每個數字 num。
    • 檢查是否為序列的起點：如果 num - 1 不在集合中，則 num 是一個可能的序列起點。
    • 擴展序列：
      • 初始化當前序列長度 currentStreak = 1。
      • 不斷檢查 num + 1 是否在集合中，若存在，則將 currentStreak 增加，並繼續檢查下一個數字。
    • 更新最大序列長度 longestStreak。
  • 為何這樣可以達到 O(n) 時間複雜度：
    • 每個數字只會被訪問兩次：一次是作為起點檢查 num - 1，一次是在序列擴展時檢查 num + 1。

程式碼

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> s(nums.begin(), nums.end());

        int ans = 0;
        for (const auto num : nums) {
            if (s.find(num) == s.end()) {
                continue;
            }

            int l = num - 1;
            while (s.find(l) != s.end()) {
                s.erase(l);
                l -= 1;
            }
            int u = num + 1;
            while (s.find(u) != s.end()) {
                s.erase(u);
                u += 1;
            }

            s.erase(num);
            ans = max(ans, u - l - 1);
        }
        return ans;
    }
};

時間與空間複雜度分析

  • 時間複雜度：O(n)
    • 分析：
      • 將數字插入 unordered_set 的時間複雜度為 O(n)。
      • 外層迴圈遍歷集合中的每個數字，內層迴圈在擴展序列時，每個數字最多被訪問一次。
      • 整體而言，每個數字最多被訪問兩次，因此總的時間複雜度為 O(n)。
  • 空間複雜度：O(n)
    • 分析：
      • 使用了額外的 unordered_set 來儲存數字，大小為 n。

Justin