另一种解题思路(已过leetcde验证,不超时)
来源:12-6 超级丑数-代码演示(2)

橙序猿哥哥
2019-07-01
首先和老师说一声Sorry,换了一种另外的思路,没有利用到堆排序,但不得不说,老师利用堆排序解决时长限制的思路很巧妙,不单单适用于这一道题。
这里面和大家分享另外一种解题思路,也是很巧妙的一种。
起始思路来自于网上大神。
相对于网上大神那种几句话简单概括思路的语句,我认为如果详细解释,其实可以用高中数学中的归纳法。
假设我们已经有了数组长度为m的元素从小到大排列的的丑数数组,那么下一个满足条件的丑数应该如何得到呢?其实无非就是一个规则
将已经有的丑数数组中每一个元素乘以primes质因数数组,得到一堆新的丑数,从其中挑选出比现有的丑数数组大的最少的那一个元素,就是下一个满足条件的丑数
说到这其实我们已经可以写出一个满足题意的代码了,缺点就是还是不满足时长限制(本人亲测),于是参考了某本书籍,在此基础上又做了一步改进。
改进的点就是不再是将所有的丑数都乘以primes质因数数组,而是新增两个和primes等长的数组,分别叫 idxPri、numPri
idxPri数组中元素满足如下条件:
ugly[ idxPri[i] - 1 ] * primes[i] <= ugly[ ugly.length-1 ]
numPri数组中元素为
numPri[i] = ugly[ idxPri[i] ] * primes[i]
有了这两个数组,每次我们找下一个丑数的时候都是找对于primes中的每一个质因子,乘以 ugly 中哪一个丑数元素比ugly中最大的丑数刚好大一点。找到这个丑数元素的下标我们将其存储到idxPri中,,存储下标与primes对应上,并把每一个质因子所产生的比ugly最大丑数大一点的那个丑数也按对应下标存到numPri中,对比numPri中谁最小,谁就应该是下一个丑数。
循环此过程,直到ugly长度达到n
具体代码如下
var nthSuperUglyNumber = function(n, primes) {
var ugly = [1]
var idxPri = new Array( primes.length ).fill(0)
var numPri = new Array( primes.length )
var last = ugly[ ugly.length-1 ]
while( n !== ugly.length ){
for( var i = 0 ; i < idxPri.length ; i++ ){
while( ugly[ idxPri[i] ] * primes[i] <= last ) {
idxPri[i]++;
}
}
for( var i= 0 ; i < idxPri.length ; i++ ){
numPri[i] = ugly[ idxPri[i] ] * primes[i]
}
ugly.push( numPri.reduce( function(a,b){ return a<b ? a : b } ) )
last = ugly[ ugly.length-1 ]
}
return ugly[ n - 1 ]
}
剑指offer上对于这种方法解释是以空间代价换时间代价,其实大家仔细看可以看出,每次找出一个丑数过程循环的次数少了很多,但是我们又额外声明了两个数组,这应该就是书上所说的空间换时间。
1回答
-
同学你做的很赞,学习算法就是要看算法的思路,这才是学习的最佳姿势,而不是纠结哪个边界.对于不同思路的算法,确实有的时候是时间换空间,还是空间换时间,这要根据不同的应用场景来选择,没有对与错之分
00
相似问题