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;    // 步長,預設為 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 不在集合中)」的數字起頭,一路往後累加計數,取最大值即可,這樣每個數字最多被走訪兩次。

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