超级丑数的另一种方法

来源: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和大家分享算法,棒棒哒

0
0

JavaScript版 数据结构与算法

填补前端同学的算法短板,掌握面试中最常见的算法与数据结构

2467 学习 · 395 问题

查看课程