263. 丑数（JS实现）

朱雀 2022-11-27 15:50 175阅读 0赞

## 1 题目 ##

> 编写一个程序，找出第 n 个丑数。  
> 丑数就是质因数只包含 2, 3, 5 的正整数。  
> 示例:  
> 输入: n = 10  
> 输出: 12  
> 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。  
> 说明:  
> 1 是丑数。  
> n 不超过1690。

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

## 2 思路 ##

**这道题我们可以使用动态规划生成丑数，可以通过动态规划优化。  
让我们从数组中只包含一个丑数数字 1 开始，使用三个指针`p1`, `p2`和 `p3`，标记所指向丑数要乘以的因子。算法很简单：在`2*nums[p1]、3*nums[p2]、5*nums[p3]`选出最小的丑数并添加到数组中。并将该丑数对应的因子指针往前走一步。重复该步骤直到计算完 1690 个丑数。**

## 3代码 ##

/** * @param {number} n * @return {number} */
    var nthUglyNumber = function(n) { 
        const res = [1];
        const map = { };
        let p1 = p2 = p3 = 0;
    
        while(res.length < n) { 
            let num = Math.min(res[p1] * 2, res[p2] * 3, res[p3] * 5);
            if (!map[num]) { 
                res.push(num);
                map[num] = true;
            }
            if (num === res[p1] * 2) { 
                p1++;
            } else if (num === res[p2] * 3) { 
                p2++;
            } else { 
                p3++;
            }
        }
    
        return res[n-1];
    };

发表评论取消回复

表情：

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

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

相关阅读

相关 LeetCode_因式分解_简单_263.丑数

目录 1.题目 2.思路 3.代码实现（Java） 1.题目丑数就是只包含质因数 2、3 和 5 的正整数。给你一个整数 n ，请你判断

悠悠/ 2023年10月06日 23:25/ 0 赞/ 62 阅读

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

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

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

相关 263. 丑数（JS实现）

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

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

相关 LeetCode263. 丑数

难度：`简单` 题目描述： > 给你一个整数 n ，请你判断 n 是否为丑数。如果是，返回 true ；否则，返回 false 。丑数就是只包含质因数 2、3

分手后的思念是犯贱/ 2022年11月17日 14:52/ 0 赞/ 36 阅读

相关 leetcode263丑数

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

矫情吗；*/ 2022年09月04日 00:41/ 0 赞/ 202 阅读

相关 leetcode 263. Ugly Number 丑数

Write a program to check whether a given number is an ugly number. Ugly numbers are pos

桃扇骨/ 2022年06月08日 13:24/ 0 赞/ 239 阅读

相关丑数

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

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

相关【LeetCode】263. 丑数

题目链接：[https://leetcode-cn.com/problems/ugly-number/description/][https_leetcode-cn.com_p

骑猪看日落/ 2022年04月21日 23:26/ 0 赞/ 231 阅读

相关丑数

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

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

相关丑数

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

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