题目如下：
把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
想法1：遍历每个自然数，判断其是否是丑数，如果是计数器+1，直到计数器为N。当然了，这是一种十分朴素的方法，代码如下：
1 int GetUglyNumber_Solution(int index) { 2 int cnt = 0; 3 int num =1; 4 while(cnt < index) 5 { 6 if(isUglyNumber(num)) 7 cnt++; 8 num++; 9 } 10 return num; 11 } 12 //依次判断每个数是不是丑数。 13 bool isUglyNumber(int n) 14 { 15 if(n==1 || n==2 || n==3 || n==5) 16 return true; 17 else if(n%2 == 0) 18 return isUglyNumber(n/2); 19 else if(n%3 == 0) 20 return isUglyNumber(n/3); 21 else if(n%5 == 0) 22 return isUglyNumber(n/5); 23 else 24 return false; 25 }
当然了这样写，在牛客网得到的结果并没有通过。原因是算法时间复杂度太大，因为我们对于每个自然数都要判断它是不是丑数，因此算法的时间复杂度很大。有没有更好的办法？
有，采用模拟三个队列的方式？也许你会问为何是队列。先看一下牛客网上别人的分析：
通俗易懂的解释： 首先从丑数的定义我们知道，一个丑数的因子只有2,3,5，那么丑数p = 2 ^ x * 3 ^ y * 5 ^ z，换句话说一个丑数一定由另一个丑数乘以2或者乘以3或者乘以5得到，那么我们从1开始乘以2,3,5，就得到2,3,5三个丑数，在从这三个丑数出发乘以2,3,5就得到4，6,10,6，9,15,10,15,25九个丑数，我们发现这种方***得到重复的丑数，而且我们题目要求第N个丑数，这样的方法得到的丑数也是无序的。那么我们可以维护三个队列： （1）丑数数组： 1 乘以2的队列：2 乘以3的队列：3 乘以5的队列：5 选择三个队列头最小的数2加入丑数数组，同时将该最小的数乘以2,3,5放入三个队列； （2）丑数数组：1,2 乘以2的队列：4 乘以3的队列：3，6 乘以5的队列：5，10 选择三个队列头最小的数3加入丑数数组，同时将该最小的数乘以2,3,5放入三个队列； （3）丑数数组：1,2,3 乘以2的队列：4,6 乘以3的队列：6,9 乘以5的队列：5,10,15 选择三个队列头里最小的数4加入丑数数组，同时将该最小的数乘以2,3,5放入三个队列； （4）丑数数组：1,2,3,4 乘以2的队列：6，8 乘以3的队列：6,9,12 乘以5的队列：5,10,15,20 选择三个队列头里最小的数5加入丑数数组，同时将该最小的数乘以2,3,5放入三个队列； （5）丑数数组：1,2,3,4,5 乘以2的队列：6,8,10， 乘以3的队列：6,9,12,15 乘以5的队列：10,15,20,25 选择三个队列头里最小的数6加入丑数数组，但我们发现，有两个队列头都为6，所以我们弹出两个队列头，同时将12,18,30放入三个队列； …………………… 疑问： 1.为什么分三个队列？ 丑数数组里的数一定是有序的，因为我们是从丑数数组里的数乘以2,3,5选出的最小数，一定比以前未乘以2,3,5大，同时对于三个队列内部，按先后顺序乘以2,3,5分别放入，所以同一个队列内部也是有序的； 2.为什么比较三个队列头部最小的数放入丑数数组？ 因为三个队列是有序的，所以取出三个头中最小的，等同于找到了三个队列所有数中最小的。 实现思路： 我们没有必要维护三个队列，只需要记录三个指针显示到达哪一步；“|”表示指针,arr表示丑数数组； （1）1 |2 |3 |5 目前指针指向0,0,0，队列头arr[0] * 2 = 2, arr[0] * 3 = 3, arr[0] * 5 = 5 （2）1 2 2 |4 |3 6 |5 10 目前指针指向1,0,0，队列头arr[1] * 2 = 4, arr[0] * 3 = 3, arr[0] * 5 = 5 （3）1 2 3 2| 4 6 3 |6 9 |5 10 15 目前指针指向1,1,0，队列头arr[1] * 2 = 4, arr[1] * 3 = 6, arr[0] * 5 = 5
当然了，也许你看完上述过程仍然不知道是怎么回事，仍然不知道为何要用到队列？上述思路告诉我们一个很重要的事实是：丑数p = 2 ^ x * 3 ^ y * 5 ^ z，因此新的丑数都是从原来的丑数中产生的；我们希望产生与已经存在的丑数不重复的最小的丑数。
下面来执行这个过程：
第一个丑数：1 求下一个丑数： <u>**2×1 = 2（min）</u>；** <u>3×1 = 3</u>； <u>5×1 = 5</u>； 挑选最小的不重复的丑数，显然是2； 前两个丑数:1，2 求下一个丑数: 2×1 = 2（该丑数已经存在）；<u>2×2 = 4</u>； <u>**3×1 = 3(min)**</u>；3×2 = 6； <u>5×1 =5</u>；5×2 = 10； 前三个丑数：1，2，3 求下一个丑数： 2×1 = 2（该丑数已经存在）；<u>**2×2 = 4(min)**</u>；2×3 = 6； 3×1 = 3（该丑数已经存在）；<u>3×2 = 6</u>；3×3 = 9； <u>5×1 =5</u>；5×2 = 10；5×3 = 15； 前四个丑数:1，2，3，4 求下一个丑数： 2×1 = 2（该丑数已经存在）；2×2 = 4（该丑数已经存在）；<u>2×3 = 6</u>，2×4 = 8； 3×1 = 3（该丑数已经存在）；<u>3×2 = 6</u>；3×3 = 9，3×4 = 12； <u>**5×1 =5(min)**</u>；5×2 = 10；5×3 = 15；5×4 = 20； 前5个丑数：1，2，3，4，5 求一下丑数： 2×1 = 2（该丑数已经存在）；2×2 = 4（该丑数已经存在）；<u>**2×3 = 6(min)**</u>，2×4 = 8，2×5 = 10； 3×1 = 3（该丑数已经存在）；<u>**3×2 = 6(min)**</u>；3×3 = 9，3×4 = 12，3×5 = 15； 5×1 =5（该丑数已经存在）；<u>5×2 = 10</u>；5×3 = 15；5×4 = 20，5×5 = 25； 前6个丑数：1，2，3，4，5，6 我们先不考虑重复丑数这种情况，上述的操作过程，用一句话总结求丑数的过程：用丑数因子2，3，5分别乘以丑数数组中的所有元素。并将最小的下一个元素加入到丑数数组中。 问题在于我们如何找最小的下一个元素？ 请记住我们的操作是什么？拿丑数因子2，3，5乘以所有的丑数数组元素。而已经存在的丑数数组是有序的。也就是意味着不同丑数因子乘以丑数数组得到的结果本身是有序的。
因此，我们只需要看不同丑数因子相乘，看“第一个”元素就好。但是我们发现了，这其中是存在重复元素的，我们总不能将重复元素加入到丑数队列中吧。
我们可以模拟三个队列，如果当前的得到的丑数来源于某个丑数因子相乘的结果（比如第二个丑数2来源于丑数因子2乘以已经存在的丑数1.）那么下一次，我将不会再做一次2×1
；因为如果你做了，必然会带来重复元素。从队列的角度讲，如果某个丑数来源于某个因子，则将这个丑数从丑数因子结果队列的头部删除。
我们仔细观察上述过程：我们发现，抛去重复元素，我们比较的永远是队首元素。，因此，其实我们并不需要真正意义的三个队列。我们只需要三个丑数因子2,3,5构成的结果数组的索引。
保证这个索引永远指在不重复数组的首部即可：
很多人不能理解的是：为什么比如2×1得到2这个新的丑数，下次对于丑数因子2而言，为什么不再计算2×1了，而是直接计算2×2了。因为2在这个丑数本身就来源于丑数数组2前面的丑数乘以丑数因子2得到的结果，如果下次求解求解最小新的不重复丑数，我们再用丑数数组2前面的丑数×丑数因子2，那么必然还会得到2，会产生重复。使得我们无法求出真正不重复的最小的。
直接上代码清晰：
1 int GetUglyNumber_Solution(int index) { 2 if(index < 7) 3 return index; 4 vector<int> ugly_nums;//缓存丑数 5 int ugly_num = 1; 6 ugly_nums.push_back(ugly_num); 7 int pt2=0,pt3=0,pt5 = 0;//分为作为乘以2，3，5三个数的指针 8 while(ugly_nums.size() < index) 9 { 10 ugly_num = min(min(2*ugly_nums[pt2],3*ugly_nums[pt3]),5*ugly_nums[pt5]); 11 if(2*ugly_nums[pt2] == ugly_num) pt2++; 12 if(3*ugly_nums[pt3] == ugly_num) pt3++; 13 if(5*ugly_nums[pt5] == ugly_num) pt5++; 14 ugly_nums.push_back(ugly_num); 15 } 16 return ugly_num; 17 }