題目

#

leetcode 128 - Longest Consecutive Sequence (題目說明請點連結)

題目簡述

#

給一個未排序的整數陣列 nums，返回最長的連續元素序列的長度。
要求演算法必須在 O(n) 時間複雜度內執行。

範例

#

Example 1:

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: 最長的連續元素序列是 [1,2,3,4]。因此其長度為 4。

Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9
Explanation: 最長的連續元素序列是 [0,1,2,3,4,5,6,7,8]。因此其長度為 9。

解題思路

#

這題要求我們找到陣列中最長的連續序列。我們可以使用HashSet來儲存所有數字，然後對於每個數字，檢查它是否是一個連續序列的起點（即沒有比它小 1 的數字），如果是，則從該數字開始計算連續序列的長度。

解法

#

s

1. 將所有數字加入 HashSet 中，方便 O(1) 查找
2. 遍歷 HashSet 中的每個數字
3. 對於每個數字，檢查它是否是一個連續序列的起點
4. 如果是起點，則從該數字開始計算連續序列的長度
5. 更新最長連續序列的長度
6. 返回最長連續序列的長度

步驟

#

• 初始化：
  • 創建 HashSet 儲存所有數字
  • 初始化最長連續序列長度 longest = 0
• 尋找連續序列：
  • 遍歷 HashSet 中的每個數字
  • 檢查數字 n 是否為連續序列的起點（!set.contains(n-1)）
  • 如果是起點，從 n 開始計算連續序列長度
• 計算序列長度：
  • 使用 while 迴圈檢查 n+length 是否在 HashSet 中
  • 更新最長連續序列長度
• 返回結果：
  • 返回最長連續序列的長度

例子說明

#

nums = [100,4,200,1,3,2]

最終結果： 4

連續序列說明：

• 序列 [100]：長度為 1
• 序列 [1,2,3,4]：長度為 4（最長）
• 序列 [200]：長度為 1

完整程式碼

#

class Solution {
    public int longestConsecutive(int[] nums) {
        // 創建 HashSet 儲存所有數字，方便 O(1) 查找
        Set<Integer> set = new HashSet<>();
       
        // 將所有數字加入 HashSet
        for(int n:nums){
            set.add(n);
        }

        // 初始化最長連續序列長度
        int longest = 0;
        
        // 遍歷 HashSet 中的每個數字
        for(int n:set){
            // 檢查數字 n 是否為連續序列的起點
            // 如果 set 中沒有 n-1，則 n 是起點
            if(!set.contains(n-1)){
                int length = 1;

                // 從 n 開始計算連續序列的長度
                while(set.contains(n+length)){
                    length ++;
                }

                // 更新最長連續序列的長度
                longest= Math.max(longest, length);
            }
         
        }

        return longest;
    }
}

時間複雜度

#

• 時間複雜度：O(n)，其中 n 是陣列的長度
  • 需要遍歷陣列一次來建立 HashSet：O(n)
  • 每個數字最多被訪問兩次（一次在建立 HashSet，一次在尋找連續序列）：O(n)
• 空間複雜度：O(n)，需要儲存 HashSet