本文共 1851 字，大约阅读时间需要 6 分钟。

264. 丑数 II

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

丑数就是质因数只包含 2, 3, 5 的正整数。

示例:输入: n = 10输出: 12解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。说明:  1 是丑数。n 不超过1690。

题解：

方法一：暴力法

即利用丑数的性质当作“判断“”来解题，因此我们只需要写下如何验证一个数是否是丑数的代码，再加以数组储存每次的丑数，当丑数的数量达到所求时再输出最后一个丑数即可，不过此法需要对从2开始的每一个数都进行验证，复杂度极高，且运行会超时。

代码：

int nthUglyNumber(int n){
       int temp = 2;//用来储存最后一个丑数    int sum = 1;    while(sum!=n)//丑数不到n个就一直循环    {
           int num = temp;//需要个中间量来完成丑数的验证过程        while(num!=1)        {
               if(num%2==0)            {
                   num=num/2;                continue;            }            else if(num%3==0)            {
                   num=num/3;                continue;            }            else if(num%5==0)            {
                   num=num/5;                continue;            }            else            {
                   goto A;            }        }        sum++;        A:temp++;    }    return temp-1;}

方法二：三指针+动态规划

此法比较考验逻辑思维以及反推的能力。因为我们的目标是求出第n个丑数，既然如此我们在寻找的时候可不可以不像方法一那样每一个数都找一遍，而是直接从丑数里一个一个找呢？这时我们可以发现可以省去验证此数是否是丑数的那段代码了，因为我们不是要去验证一个数是否是丑数。

依次我们会思考，如何使得我们找的每个数都是丑数？

因此我们发现我们只需要调整一下寻找数字时两数之间的跨度即可。

方法一中我们是每一个数字都寻找了，因此我们的跨度是1，我们这里只需要修改跨度即可。

#我们这里采用三指针+动态规划来完成上述的描绘过程：

首先由于上述可知，我们算下一个丑数时为了减少计算量，是需要前面的丑数的大小数据的，即直接在前面丑数的基础上乘对应的2，3，5可以更快达到自己想得到的丑数。因此我们可以创建一个数组来保存你找到的丑数，且从小到大排列。

接着设立三个指针，它们分别对应乘的2，3，5的个数（代码中对应的是个数-1），接着进入循环，即不找到n个丑数不出去的循环。

为了满足从小到大寻找丑数，我们创建一个least函数找出在丑数1的基准上乘若干个2,3,5之后形成的最小的丑数，找到后把他放进数组内，接着改变一下他对应指针的指向位置（即它们乘的2，3，5个数），然后进入下次循环。

代码：

//新思路：三指针法,第一个丑数设为1，接着不断用235乘以它们指针所在的位置，比较谁小的方法，如果采用某一指针，则指针进一；int least(int x,int y,int z){
       int temp = x

转载地址：https://blog.csdn.net/xiangguang_fight/article/details/114544189 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！