DIV CSS 佈局教程網

JavaScript 找出陣列中最長的連續數字序列
編輯:JavaScript綜合知識     

題目是這樣的:給定一個無序的整數序列,找出其中最長的一段連續數字。例如輸入 [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,然後逐一檢查「該數字減一是否存在」——只有不存在時才代表它是某段序列的起點,接著往上累加連續的數字並記錄最大長度。這個寫法不需要排序,程式碼也更短,是很值得一試的思路。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved