国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

不可變數組的范圍求和

gitmilk / 1581人閱讀

摘要:二維表二維表可以將每一對完全映射一個值,這樣的話,空間復雜度變成了,記得我們前面說了,這個數組可能會很大,有個元素,如果用這樣的映射表,內存就溢出了。

給定一個整數數組 nums,計算出從第 i 個元素到第 j 個元素的和 ( i ≤ j ),包括 nums[ i ] 和 nums[ j ]。
例子:

const nums = Object.freeze([-2, 0, 3, -5, 2, -1]);

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

注意:

假定數組的值不會改變(如上面代碼,nums 因為 Object.freeze 的緣故可讀不可寫)
sumRange 可能會被使用很多次,求不同范圍的值
數組可能規模很大(比如超過 10000 個數),注意運行時間

解題思路

這道題看起來十分簡單對吧,簡單寫一個函數應該誰都會:

const Immutable = Sup => class extends Sup {
  constructor(...args){
    super(...args);
    Object.freeze(this);
  }
}

class NumArray extends Immutable(Array){
  sumRange(i, j){
    let sum = 0;
    for(; i <= j; i++){
      sum += this[i];
    }
    return sum;    
  }
}

上面的代碼里面我們重構了數組,這里我用了一點點小技巧來讓數組元素不可變,這個技巧在我之前的一篇譯文“六個漂亮的 ES6 技巧”中被提到,很多同學不理解那篇文章的第6個技巧,在這里我使用了一下,當然這無關我們今天討論的主題。

于是我們可以用新的數組對象來計算 sumRange:

var nums = new NumArray(-2, 0, 3, -5, 2, -1);

nums.sumRange(0, 2) -> 1
nums.sumRange(2, 5) -> -1
nums.sumRange(0, 5) -> -3

到這里為止,我們似乎并沒有改變什么,我們只是繼承了 Array 類,把 sumRange 改成了對象的方法而已,它還是一樣很慢。

那接下來我們要怎么做呢?

因為前面說過了,sumRange 要被調用很多次,所以我們要盡可能減少 sumRange 調用的復雜度對嗎?按照前面的方式,我們用一個循環來對從 i 到 j 進行求和,有沒有更快的方法?答案是:空間換時間,查表!
查表

查表不是查水表,因為 sumRange 要計算很多次,所以我們可以事先在 NumArray 構造的時候將 sumRange 需要查的值算好存入一個表中。

二維表?
R/C 0 1 2 3 4 5
0 -2 -2 1 -4 -2 -3
1 0 3 -2 0 -1
2 3 -2 0 -1
3 -5 -3 -4
4 2 1
5 -1

二維表可以將每一對 i, j 完全映射一個值,這樣的話,空間復雜度變成了 O( n2 ),記得我們前面說了,這個數組可能會很大,有 10000 個元素,如果用這樣的映射表,內存就溢出了。實際上,使用二維表是愚蠢的,因為我們可以很容易找到以下對應關系:

sumRange(i, j) === sumRange(0, j) - sumRange(0, i - 1); //(i > 0)

一維表

我們只需要將 NumArray 的每一個元素對應從第 1 元素開始求和,將結果保存成一個一維表,我們就可以用 O( 1 ) 時間復雜度來計算 sumRange( i, j ) !

以下是經過優化之后的 NumArray:

const UniqueID = Sup => class extends Sup {
  constructor(...args){
      super(...args);
      Object.defineProperty(this, "id", {
        value: Symbol(),
        writable: false,
        enumerable: false
      });
    }
}

const Immutable = Sup => class extends Sup {
  constructor(...args){
    super(...args);
    Object.freeze(this);
  }
}

const NumArray = (function(){
  let sumTable = {};
  return class  extends Immutable(UniqueID(Array)){
    constructor(...args){
      super(...args);
      let sum = 0;
      let table = [0];

      for(let i = 0; i < this.length; i++){
        sum += this[i];
        table.push(sum);
      }
      sumTable[this.id] = table;
    }
    sumRange(i, j){
      let table = sumTable[this.id];
      return table[j + 1] - table[i];   
    }
  }
})();

上面的代碼里,我們在構造 NumArray 的時候同時創建了一個私有屬性 sumTable,它的第 1 個元素是 0,第 i + 1 個元素等于 sumRange(0, i),因此我們就可以快速通過:

sumRange(i, j){
  let table = sumTable[this.id];
  return table[j + 1] - table[i];   
}

來計算出 sumRange(i, j) 的值了。

進一步優化

上面的代碼通過查表大大加快了 sumRange 的執行速度,由于數組 NumArray 是不可變的,因此我們在它被構造的時候創建好 sumTable,那么 sumRange 就完全只需要查表加上一次減法運算就可以完成了。這么做提升了 sumRange 的性能,代價是構造 NumArray 對象的時候帶來額外的建表開銷。

不過,我們可以不在構造對象的時候建表,而在對象的 sumRange 方法第一次被使用的時候建表。這樣的話,我們就將性能開銷延從構造對象時遲到了第一次使用 sumRange 時,如果恰巧某種原因,NumArray 對象沒有被使用,那么 sumTable 就永遠也不會被創建。看下面的代碼:

將創建 sumTable 的工作放在 sumRange 第一次被調用時

const UniqueID = Sup => class extends Sup {
  constructor(...args){
    super(...args);
    Object.defineProperty(this, "id", {
      value: Symbol(),
      writable: false,
      enumerable: false
    });
  }
};

const Immutable = Sup => class extends Sup {
  constructor(...args){
    super(...args);
    Object.freeze(this);
  }
};

const NumArray = (function(){
  let sumTable = {};
  return class  extends Immutable(UniqueID(Array)){
    sumRange(i, j){
      if(!sumTable[this.id]){
        let table = [0], sum = 0;
        for(let i = 0; i < this.length; i++){
          sum += this[i];
          table.push(sum);
        }
        sumTable[this.id] = table;
      }
      let table = sumTable[this.id];
      return table[j + 1] - table[i];
    }
  }
})();

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/50491.html

相關文章

  • 可變數組范圍求和

    摘要:二維表二維表可以將每一對完全映射一個值,這樣的話,空間復雜度變成了,記得我們前面說了,這個數組可能會很大,有個元素,如果用這樣的映射表,內存就溢出了。 給定一個整數數組 nums,計算出從第 i 個元素到第 j 個元素的和 ( i ≤ j ),包括 nums[ i ] 和 nums[ j ]。例子: const nums = Object.freeze([-2, 0, 3, -5, 2...

    lansheng228 評論0 收藏0
  • 可變數組范圍求和

    摘要:二維表二維表可以將每一對完全映射一個值,這樣的話,空間復雜度變成了,記得我們前面說了,這個數組可能會很大,有個元素,如果用這樣的映射表,內存就溢出了。 給定一個整數數組 nums,計算出從第 i 個元素到第 j 個元素的和 ( i ≤ j ),包括 nums[ i ] 和 nums[ j ]。例子: const nums = Object.freeze([-2, 0, 3, -5, 2...

    luzhuqun 評論0 收藏0
  • 可變數組范圍求和

    摘要:二維表二維表可以將每一對完全映射一個值,這樣的話,空間復雜度變成了,記得我們前面說了,這個數組可能會很大,有個元素,如果用這樣的映射表,內存就溢出了。 給定一個整數數組 nums,計算出從第 i 個元素到第 j 個元素的和 ( i ≤ j ),包括 nums[ i ] 和 nums[ j ]。例子: const nums = Object.freeze([-2, 0, 3, -5, 2...

    BicycleWarrior 評論0 收藏0
  • java可變參數

    摘要:可變參數是之后出現的新特性使用前提當方法的參數列表數據類型已經確定但是參數的個數不確定就可以使用可變參數使用格式定義方法時使用修飾符返回值類型方法名數據類型變量名可變參數的原理可變參數底層就是一個數組根據傳遞參數個數不同會創建不同長度的數組 package com.itheima.demo04.VarArgs;/* 可變參數:是JDK1.5之后出現的新特性 使用前提: 當方法的...

    yeooo 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<