原始題目:給定一個無序的整數序列,找出最長的連續數字序列。
例如,給定 [100, 4, 200, 1, 3, 2],最長的連續數字序列是 [1, 2, 3, 4]。
以下提供解法:
function maxSequence(array,step){ var _array = array.slice(), //clone array _step = 1, _arrayTemp = [], i = 0; var parseLogic = { parseResults: [], set: function(n){ this.parseResults[this.parseResults.length-1].push(n); }, get: function(){ return this.parseResults[this.parseResults.length-1]; }, 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; }); //remove repeat of data 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); //return [2,3,4,5] maxSequence([5,7,2,4,0,3,9],2); //return [5,7,9]
整體思路是先排序並去重,再遍歷比對相鄰元素是否符合步長關係,最後從所有候選序列中挑出最長的一組。