摘要:二维表二维表可以将每一对完全映射一个值,这样的话,空间复杂度变成了,记得我们前面说了,这个数组可能会很大,有个元素,如果用这样的映射表,内存就溢出了。
给定一个整数数组 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]; } } })();
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/38458.html
摘要:二维表二维表可以将每一对完全映射一个值,这样的话,空间复杂度变成了,记得我们前面说了,这个数组可能会很大,有个元素,如果用这样的映射表,内存就溢出了。 给定一个整数数组 nums,计算出从第 i 个元素到第 j 个元素的和 ( i ≤ j ),包括 nums[ i ] 和 nums[ j ]。例子: const nums = Object.freeze([-2, 0, 3, -5, 2...
摘要:二维表二维表可以将每一对完全映射一个值,这样的话,空间复杂度变成了,记得我们前面说了,这个数组可能会很大,有个元素,如果用这样的映射表,内存就溢出了。 给定一个整数数组 nums,计算出从第 i 个元素到第 j 个元素的和 ( i ≤ j ),包括 nums[ i ] 和 nums[ j ]。例子: const nums = Object.freeze([-2, 0, 3, -5, 2...
摘要:二维表二维表可以将每一对完全映射一个值,这样的话,空间复杂度变成了,记得我们前面说了,这个数组可能会很大,有个元素,如果用这样的映射表,内存就溢出了。 给定一个整数数组 nums,计算出从第 i 个元素到第 j 个元素的和 ( i ≤ j ),包括 nums[ i ] 和 nums[ j ]。例子: const nums = Object.freeze([-2, 0, 3, -5, 2...
阅读 1706·2021-09-26 09:46
阅读 2955·2021-09-22 15:55
阅读 2579·2019-08-30 14:17
阅读 2994·2019-08-26 11:59
阅读 1769·2019-08-26 11:35
阅读 3121·2019-08-26 10:45
阅读 3114·2019-08-23 18:28
阅读 992·2019-08-23 18:21