超级丑数的另一种方法
来源:12-6 超级丑数-代码演示(2)

MeSKiL
2019-10-08
老师,我这里根据计算第n个丑数的值的方法,解出了这道题计算第n个超级丑数方法。
计算第n个丑数的方法是这样的
var nthUglyNumber = function(n) {
let index2 = 0;
let index3 = 0;
let index5 = 0;
let arr = [1];
for(let i=1;i<n;i++){
arr[i] = Math.min(2*arr[index2],3*arr[index3],5*arr[index5]);
if(arr[i]===2*arr[index2]){
index2++
}
if(arr[i]===3*arr[index3]){
index3++
}
if(arr[i]===5*arr[index5]){
index5++
}
}
return arr[n-1]
};
如果一个数是丑数,那么这个数乘以2乘以3乘以5就都是丑数
那么就可以这样,比如初始的数组为[1],我们就用1乘以2,乘以3,乘以5,得到2,3,5,最小的是2,所以将2加入数组中,数组为[1,2]。
然后因为1乘2已经使用过了,但是1乘以3和1乘以5还没有使用过,所以判断 2乘以2 1乘以3 1乘以5 也就是
4(2×2) 3(3×1) 5 (5×1)的最小值,3加入数组。
之后就是判断 4(2×2)6(3×2)5(5×1)的最小值4加入数组,
而后就是6(2×3) 6(3×2) 5(5×1) 的最小值5,
之后是 6(2×3) 6(3×2) 10(5×2)
8(2×4) 9(3×3) 10(5×2)
以此类推就按顺序将丑数添加到了结果中
超级丑数也是同理就实现了!
var superUglyNumber = function(n,primes) {
let indexArr = primes.map(item => 0); // indexArr为长度与primes相同,值皆为0的数组
let arr = [1];
for(let i=1;i<n;i++){
let result = primes.map((item,index) => {
return item*arr[indexArr[index]]
});
// result为 primes的各项值乘以与他对应的indexArr中的index的值
arr[i] = Math.min(...result);
// 取result中的最小值
for(let j=0,len=result.length;j<len;j++){
if(arr[i]===result[j]){
indexArr[j]++
}
// 命中的result相对应的index加一
}
}
return arr[n-1]
};
写回答
1回答
-
快乐动起来呀
2019-10-08
可以在leetcode提交代码测试下所有测试用例,如果能通过建议放在git的issue和大家分享算法,棒棒哒
00
相似问题