寻找第n个丑数

骑猪看日落 2023-07-10 14:27 28阅读 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))

执行结果如下所示：

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