題目是這樣的:給定一個無序的整數序列,找出其中最長的一段連續數字。例如輸入 [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;
// 由小到大排序
_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) 時間複雜度,以及為了解耦而寫的 parseLogic 物件讓程式碼變得偏長。若只追求效率,其實存在 O(n) 的做法:把全部數字丟進 Set,然後逐一檢查「該數字減一是否存在」——只有不存在時才代表它是某段序列的起點,接著往上累加連續的數字並記錄最大長度。這個寫法不需要排序,程式碼也更短,是很值得一試的思路。