313. 超级丑数（JS实现）

￡神魔★判官ぃ 2022-11-27 15:59 168阅读 0赞

## 1 题目 ##

> 编写一段程序来查找第 n 个超级丑数。  
> 超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数。  
> 示例:  
> 输入: n = 12, primes = \[2,7,13,19\]  
> 输出: 32  
> 解释: 给定长度为 4 的质数列表 primes = \[2,7,13,19\]，前 12 个超级丑数序列为：\[1,2,4,7,8,13,14,16,19,26,28,32\] 。  
> 说明:  
> 1 是任何给定 primes 的超级丑数。  
> 给定 primes 中的数字以升序排列。  
> 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes\[i\] < 1000 。  
> 第 n 个超级丑数确保在 32 位有符整数范围内。

链接：https://leetcode-cn.com/problems/super-ugly-number

## 2 思路 ##

**这道题和之前丑数二有点类型，区别在于这里的质数数组为输入参数，而不再是固定的了，但本质上不变，在原来的动态规划的基础上增加一个循环即可**

## 3代码 ##

/** * @param {number} n * @param {number[]} primes * @return {number} */
    var nthSuperUglyNumber = function(n, primes) { 
        const res = [1];
        let p = [];
        for (let i=0;i<primes.length;i++){    //初始化指针
            p.push(0);
        }
        let prev;
        let minIndex = 0;
        while(res.length < n) { 
            let min = res[p[minIndex]] * primes[minIndex];  //初始化最小值
            for (let i=0;i<primes.length;i++){     //循环比较获取当前最小乘积
                let num = res[p[i]] * primes[i];   
                min = Math.min(min, num);
                if (min === num) minIndex = i;
            }
            if (prev !== min) res.push(min);     //用于去重
            prev = min;
            p[minIndex]++;
        }
    
        return res[res.length - 1];
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，168人围观）

还没有评论，来说两句吧...

相关阅读

相关 313. 超级丑数（JS实现）

1 题目 > 编写一段程序来查找第 n 个超级丑数。 > 超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数。 > 示例: > 输入

￡神魔★判官ぃ/ 2022年11月27日 15:59/ 0 赞/ 168 阅读

相关 263. 丑数（JS实现）

1 题目 > 编写一个程序，找出第 n 个丑数。 > 丑数就是质因数只包含 2, 3, 5 的正整数。 > 示例: > 输入: n = 10 > 输出:

朱雀/ 2022年11月27日 15:50/ 0 赞/ 124 阅读

相关丑数

\\题目描述把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。习惯上我们把1当做是第一个丑数。求按从小到

r囧r小猫/ 2022年10月27日 13:48/ 0 赞/ 170 阅读

相关 leetcode313超级丑数

参考264和263 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ib

待我称王封你为后i/ 2022年09月04日 00:42/ 0 赞/ 160 阅读

相关丑数

把只包含因子2、3和5的数称作丑数，例如6，8都是丑数，但14不是，因为它包含因子7，习惯上我们把1当作第一个丑数，求按从小到大的顺序的第N个丑数。输入描述：整数N

小咪咪/ 2022年06月08日 08:52/ 0 赞/ 207 阅读

相关 leetcode 313. Super Ugly Number 超级丑数

Write a program to find the nth super ugly number. Super ugly numbers are positive numb

男娘i/ 2022年06月07日 01:06/ 0 赞/ 138 阅读

相关丑数

求第1500个丑数。丑数是不能被2.3.5之外的其他素数整除的数，把丑数从小到大排起来，然后打印第1500个先写一个典例，我写的， //这是我写的，运行了大概15

你的名字/ 2022年05月18日 10:55/ 0 赞/ 178 阅读

相关丑数

时间限制：1秒空间限制：32768K 热度指数：223966 本题知识点：数组算法知识视频讲解题目描述把只包含质因子2、3和5的数称作丑数（Ugly

本是古典何须时尚/ 2022年03月09日 10:50/ 0 赞/ 259 阅读

相关丑数

列表res按序存储丑数 res\[0\] = 1，下一个丑数产生规则： 1.找出res所有数\2 中第一个大于 res \[-1\] 的数：res\[n2\] 2

迷南。/ 2022年01月30日 07:43/ 0 赞/ 229 阅读

相关丑数

丑数就是只包含质因数 2, 3, 5 的正整数。 1.判断丑数 2.找到第n个丑数（代码很容易看懂） public class UglyNum {

梦里梦外;/ 2021年09月26日 23:24/ 0 赞/ 326 阅读