給定無序整數陣列,找出最長連續數字序列 (步長可自訂)。本文提供排序後單趟掃描的標準解法,支援自訂步長、去重、多序列比較,並分析時間複雜度與邊界情況處理。
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, []);
}
/**
* 找出陣列中最長的等差數列 (連續序列)
* @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) | 瓶頸在排序 |
若不需輸出序列本身,只需長度,可用 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;
}
// 但無法直接得到序列內容 (需額外記錄)
array.sort() 會副作用,務必展開運算子複製=== 比較會失效,需乘倍數轉整數「排序 + 去重 + 單趟分組」是取得最長連續序列內容的標準解法,O(n log n) 時間、O(n) 空間,程式碼清晰易維護。若僅需長度,Set 查找法可達 O(n)。實務中根據資料量、是否需序列內容、步長固定與否選擇適當演算法。