萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 腳本程式專題 >> JavaScript

JavaScript 找出陣列最長連續數字序列:排序+單趟掃描 O(n log n) 解法

給定無序整數陣列,找出最長連續數字序列 (步長可自訂)。本文提供排序後單趟掃描的標準解法,支援自訂步長、去重、多序列比較,並分析時間複雜度與邊界情況處理。

題目範例

input:  [100, 4, 200, 1, 3, 2]
output: [1, 2, 3, 4] // 最長連續序列,步長 1

// 步長 2
input:  [5, 7, 2, 4, 0, 3, 9]
output: [5, 7, 9] // 步長 2 的最長序列

核心演算法:排序 + 單趟分組

function maxSequence(array, step = 1) {
    if (!array || !array.length) return [];
    
    // 1. 複製並排序 (不修改原陣列)
    const sorted = [...array].sort((a, b) => a - b);
    
    // 2. 去重 (排序後相鄰比較 O(n))
    const unique = [];
    for (let i = 0; i < sorted.length; i++) {
        if (sorted[i] !== sorted[i + 1]) {
            unique.push(sorted[i]);
        }
    }
    
    // 3. 單趟掃描分組連續序列
    const sequences = [];
    let current = [unique[0]];
    
    for (let i = 1; i < unique.length; i++) {
        if (unique[i] - unique[i - 1] === step) {
            current.push(unique[i]); // 連續,加入當前序列
        } else {
            sequences.push(current); // 斷開,存檔當前序列
            current = [unique[i]];   // 開始新序列
        }
    }
    sequences.push(current); // 別忘了最後一組
    
    // 4. 找出最長序列
    return sequences.reduce((longest, seq) => 
        seq.length > longest.length ? seq : longest, []);
}

完整可執行版本 (含參數驗證、JSDoc)

/**
 * 找出陣列中最長的等差數列 (連續序列)
 * @param {number[]} array - 輸入整數陣列
 * @param {number} [step=1] - 步長/公差,預設 1
 * @returns {number[]} 最長連續序列 (不修改原陣列)
 */
function maxSequence(array, step = 1) {
    // 參數驗證
    if (!Array.isArray(array)) throw new TypeError('第一參數必須是陣列');
    if (array.length === 0) return [];
    if (!Number.isInteger(step) || step <= 0) throw new Error('step 必須為正整數');
    
    // 排序 + 去重
    const sorted = [...array].sort((a, b) => a - b);
    const unique = sorted.filter((val, i, arr) => i === 0 || val !== arr[i - 1]);
    
    // 分組連續序列
    const sequences = [];
    let current = [unique[0]];
    
    for (let i = 1; i < unique.length; i++) {
        if (unique[i] - unique[i - 1] === step) {
            current.push(unique[i]);
        } else {
            sequences.push(current);
            current = [unique[i]];
        }
    }
    sequences.push(current);
    
    // 找最長 (若多組同長,回傳第一組)
    return sequences.reduce((max, seq) => seq.length > max.length ? seq : max, []);
}

測試案例

console.log(maxSequence([100, 4, 200, 1, 3, 2]));           // [1, 2, 3, 4]
console.log(maxSequence([5, 7, 2, 4, 0, 3, 9], 1));         // [2, 3, 4, 5]
console.log(maxSequence([5, 7, 2, 4, 0, 3, 9], 2));         // [5, 7, 9]
console.log(maxSequence([1, 1, 2, 2, 3, 3]));               // [1, 2, 3] (去重)
console.log(maxSequence([10, 20, 30], 10));                 // [10, 20, 30]
console.log(maxSequence([], 1));                            // []
console.log(maxSequence([42]));                             // [42]
console.log(maxSequence([3, 1, 2, 5, 4]));                  // [1, 2, 3, 4, 5]

// 邊界:負數、零
console.log(maxSequence([-3, -1, 0, 1, 2]));                // [-1, 0, 1, 2] 或 [0,1,2] 視去重

時間/空間複雜度分析

階段時間空間說明
排序O(n log n)O(n) 或 O(log n)JS 引擎 Timsort/Quicksort
去重O(n)O(n)新陣列
分組掃描O(n)O(n)最坏全不連續,每個元素獨立成序列
找最長O(k)O(1)k=序列數 ≤ n
總計O(n log n)O(n)瓶頸在排序

進階:O(n) 解法 (集合查找法)

若不需輸出序列本身,只需長度,可用 Set 達到 O(n):

function longestConsecutiveLength(nums) {
    const set = new Set(nums);
    let maxLen = 0;
    
    for (const num of set) {
        // 只有序列起點才展開 (num-1 不在集合中)
        if (!set.has(num - 1)) {
            let current = num;
            let len = 1;
            while (set.has(current + 1)) {
                current++;
                len++;
            }
            maxLen = Math.max(maxLen, len);
        }
    }
    return maxLen;
}
// 但無法直接得到序列內容 (需額外記錄)

實務應用場景

  • 股票連漲/連跌天數分析
  • 用戶連續登入天數統計
  • 日誌時間戳連續性檢測
  • 基因序列分析
  • 遊戲連擊/連續成就判定

常見錯誤避坑

  1. 未去重:重複數字會干擾連續判斷
  2. 修改原陣列:直接 array.sort() 會副作用,務必展開運算子複製
  3. 步長為 0 或負數:邏輯錯誤,需參數驗證
  4. 忽略空陣列/單元素:邊界情況處理
  5. 浮點數精度:輸入若含浮點數,=== 比較會失效,需乘倍數轉整數

總結

「排序 + 去重 + 單趟分組」是取得最長連續序列內容的標準解法,O(n log n) 時間、O(n) 空間,程式碼清晰易維護。若僅需長度,Set 查找法可達 O(n)。實務中根據資料量、是否需序列內容、步長固定與否選擇適當演算法。

copyright © 萬盛學電腦網 all rights reserved