寻找第n个丑数

骑猪看日落 2023-07-10 14:27 3阅读 0赞

### 寻找第n个丑数 ###

*  应用案例
 *  案例分析
 *   *   *  丑数的概念
         *  过程分析
 *  代码实现

# 应用案例 #

编写一个程序，找出第n个丑数。

# 案例分析 #

### 丑数的概念 ###

一个数的因子仅仅包括2，3，5的数称为丑数。

**说明1**：数字1特别对待也看作是丑数。  
**说明2**：从1开始的10个丑数分别为1，2。3。4，5，6，8，9。10。12。

### 过程分析 ###

该题理解的关键之处在于：**从丑数分解出来的因子，一定是一个丑数，即丑数一定是由丑数相乘得到的**。所以，丑数的2，3，5倍均是一个丑数。

所以该题的核心为：默认第一个丑数是1，用第一个丑数 1 做 1×2；1×3；1×5；从这三个数字中选择一个最小的即为第二个丑数，结果是2；然后分别求第一个丑数和第二个丑数的2/3/5倍（除去已有的丑数2），取最小的作为第三个丑数；以此类推，求每个丑数的2/3/5倍，并作比较取最小的。

具体分析过程如下图：  
![在这里插入图片描述][20200303131044176.gif]

# 代码实现 #

def getUglyNum(index):
        if index < 1:
            return 0
    
        #默认第一个丑数
        res = [1]
    
        #t2、t3、t5是丑数列表res的下标
        t2 = t3 = t5 = 0
        nextdex = 1
    
        while nextdex < index:
            minNum = min(res[t2] * 2, res[t3] * 3, res[t5] * 5)
            res.append(minNum)
    
            #注意：这里是使用三个while循环，而不用if...else...
            #当上述执行到第5步时，存在两个元素的结果相同的情况
           
            while res[t2] * 2 <= minNum:
                t2 += 1
            while res[t3] * 3 <= minNum:
                t3 += 1
            while res[t5] * 5 <= minNum:
                t5 += 1
            nextdex += 1
        return res[nextdex-1]
    print(getUglyNum(10))

执行结果如下所示：

12

[20200303131044176.gif]: https://img-blog.csdnimg.cn/20200303131044176.gif

发表评论取消回复

表情：

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

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

相关阅读

相关找到第n个数，

find the nth digit Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K

「爱情、让人受尽委屈。」/ 2024年02月18日 23:15/ 0 赞/ 7 阅读

相关 N33_丑数

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

た入场券/ 2023年08月17日 17:36/ 0 赞/ 71 阅读

相关寻找第n个丑数

寻找第n个丑数应用案例案例分析丑数的概念过程分析代码实现应用案例编写一个程序，找出第n个丑

骑猪看日落/ 2023年07月10日 14:27/ 0 赞/ 4 阅读

相关丑数

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

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

相关 162-求第N个丑数的值

什么是丑数？把只包含质因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数，但7、14不是，因为它们包含质因子7。习惯上我们把1当做是第一个丑数。

我会带着你远行/ 2022年10月24日 13:27/ 0 赞/ 153 阅读

相关丑数

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

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

相关丑数

求第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 赞/ 231 阅读

相关丑数

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

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