題目:給定一個無序整數序列,找出其中最長的連續數字序列。
例如輸入 [100, 4, 200, 1, 3, 2],最長的連續序列是 [1, 2, 3, 4]。
以下是一種解法:
function maxSequence(array, step) {
var _array = array.slice(), // 複製一份,不改動原數組
_step = 1,
_arrayTemp = [],
i = 0;
var parseLogic = {
// 結果容器
parseResults: [],
// 把值放進 parseResults 的最後一個子數組
set: function (n) {
this.parseResults[this.parseResults.length - 1].push(n);
},
// 取出 parseResults 的最後一個子數組
get: function () {
return this.parseResults[this.parseResults.length - 1];
},
// 在 parseResults 中新增一個子數組
addItem: function () {
this.parseResults.push([]);
},
// 依長度升冪排序
sortByAsc: function () {
this.parseResults.sort(function (a, b) {
return a.length - b.length;
});
}
};
_step = step || _step; // 步長,預設為 1
// 數組升冪排序
_array.sort(function (a, b) { return a - b; });
// 去除重複值
for (i = 0; i < _array.length; i++) {
if (_array[i] != _array[i + 1]) {
_arrayTemp.push(_array[i]);
}
}
_array = _arrayTemp.slice();
_arrayTemp = [];
// 分組解析
parseLogic.addItem();
for (i = 0; i < _array.length; i++) {
if (_array[i] + _step == _array[i + 1]) {
parseLogic.set(_array[i]);
continue;
}
if (_array[i] - _step == _array[i - 1]) {
parseLogic.set(_array[i]);
parseLogic.addItem();
}
}
// 排序後取出最長的一組
parseLogic.sortByAsc();
return parseLogic.get();
}
方法名稱:maxSequence(array, step)
參數:
array:要搜尋的數組,必填。
step:序列步長(增量),可選,預設為 1。
返回值:不會改動傳入的數組,回傳一個包含最長序列的新數組。
調用示例:
maxSequence([5,7,2,4,0,3,9], 1); // 回傳 [2,3,4,5]
maxSequence([5,7,2,4,0,3,9], 2); // 回傳 [5,7,9]
這個實作的思路是「排序 → 去重 → 依步長分組 → 取最長組」,時間複雜度主要落在排序上,約為 O(n log n)。如果想再往下優化到 O(n),可以改用 Set:先把所有數字放進集合,接著只從「沒有前驅(num - step 不在集合中)」的數字起頭,一路往後累加計數,取最大值即可,這樣每個數字最多被走訪兩次。