128. Longest Consecutive Sequence

Leetcode 問題: 128. Longest Consecutive Sequence
Categories:
Tags:

題目

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

傳入一個整數陣列 nums，取得最長的連續整數長度

Example

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
整數陣列 nums 100 4 200 1 3 2
連續整數 4 1 3 2 
Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

演算法

1. 建立數字陣列的 Set，只取唯一值

使用 Set 確定每個數字是否有出現，不紀錄重複出現的數字

2. 找到每個連續整數的起點

要計算 連續整數 的長度，必須從頭開始計算，所以必須要找到每個 連續整數 的起點在哪個位置

連續整數 的起點代表他是 第 1 個 數字，所以表示 前面沒有任何數字比他小

所以可以找 每個數字 - 1 確認是否存在這個數字

  • 不存在：這個數是 連續整數 的起點 第 1 個 數字
  • 不存在：這個數不是 連續整數 的起點數字

3. 尋找所有連續整數長度

找到 連續整數 的起點數字後，計算這個 連續整數 的長度

然後比較「最長連續整數長度」與「目前整數為起點，連續整數的長度」，取最長的那一個

答案

JavaScript

function longestConsecutive(numsList) {
    // 建立數字陣列的 Set，只取唯一值
    var NumsListSet = new Set(numsList);
    // 設定最長連續整數長度，預設是 0
    var longestConsecutiveNumberLength = 0;
    NumsListSet.forEach(function (currentNumber) {
        // 如果有前一個數字，前一個數字的值是
        var previousNumber = currentNumber - 1;
        if (!NumsListSet.has(previousNumber)) {
            // 如果沒有前一個數字，表示這個是「連續整數」的第 1 個整數
            // 計算以目前整數為起點，連續整數的長度是多少
            var currentNumberConsecutiveNumberLength = 0;
            while (NumsListSet.has(currentNumber + currentNumberConsecutiveNumberLength)) {
                // 從頭開始計算連續的整數數量，直到找不到連續的整數
                currentNumberConsecutiveNumberLength++;
            }
            // 比較「最長連續整數長度」與「目前整數為起點，連續整數的長度」，取最長的那一個
            longestConsecutiveNumberLength = Math.max(longestConsecutiveNumberLength, currentNumberConsecutiveNumberLength);
        }
    });
    return longestConsecutiveNumberLength;
}

TypeScript

function longestConsecutive(numsList: number[]): number {
    // 建立數字陣列的 Set，只取唯一值
    const NumsListSet = new Set(numsList);

    // 設定最長連續整數長度，預設是 0
    let longestConsecutiveNumberLength = 0;

    NumsListSet.forEach((currentNumber) => {
        // 如果有前一個數字，前一個數字的值是
        let previousNumber = currentNumber - 1;
        if (!NumsListSet.has(previousNumber)) {
            // 如果沒有前一個數字，表示這個是「連續整數」的第 1 個整數
            // 計算以目前整數為起點，連續整數的長度是多少
            let currentNumberConsecutiveNumberLength = 0;
            while (NumsListSet.has(currentNumber + currentNumberConsecutiveNumberLength)) {
                // 從頭開始計算連續的整數數量，直到找不到連續的整數
                currentNumberConsecutiveNumberLength++;
            }

            // 比較「最長連續整數長度」與「目前整數為起點，連續整數的長度」，取最長的那一個
            longestConsecutiveNumberLength = Math.max(longestConsecutiveNumberLength, currentNumberConsecutiveNumberLength);
        }
    });


    return longestConsecutiveNumberLength;
};

參考資料