题目：我们把只包含因子2，3和5的数称作为丑数。求按从小到大的顺序的第1500个丑数。例如6，8都是丑数，但是14不是，因为它包含因子7。习惯上我们把1作为第一个丑数。
方法一：遍历法
使用遍历法求第k个丑数，从1开始遍历，如果是丑数则count++，直到count==k为止。那么如何判断丑数呢？根据丑数的定义，丑数只有2，3，5这三个因子，那么我们就拿数字除以这三个因子。具体算法如下:
- 如果一个数能够被2整除，那么让他继续除以2；
- 如果一个数能够被3整除，那么让他继续除以3；
- 如果一个数能够被5整除，那么让他继续除以5；
- 如果最后这个数变为1，那么这个数就是丑数，否则不是。
代码实现如下：
View Code
其运行结果如下：
我们发现一共耗时33秒，性能比较低。
方法二：创建丑数数组，用空间还时间
如前所述，我们发现采用遍历法求第K个丑数的效率十分低下，我们在前面求第1500个丑数花去了33秒的时间，这还是在我I7 3770K的电脑上运行的。所以我们考虑有没有一种更加高效的方法。在面试题9：斐波那契数列中我们使用了一种“用空间还时间”的方法来提高求斐波那契数列的速度。这种编程思想也可以应用在这道题目当中，我们为所有求出的丑数创建数组，不在非丑数上面浪费时间。
根据丑数的定义，我们可以知道丑数可以由另外一个丑数乘以2，3或者5得到。因此我们创建一个数组，里面的数字是排好序的丑数，每一个丑数都是前面的丑数乘以2，3或者5得到的。这种思路的关键在于怎样确保数组里面的数字是排序的。
假设丑数数组中已经有若干个排好序的丑数，比如1，2，3，4，5。我们把当前丑数数组中的最大数记为M，这里M=5。我们接下来分析如何生成下一个丑数。根据前面的介绍，我们知道这个丑数肯定是前面丑数数组中的数字乘以2，3，5得到的。所以我们首先考虑把已有的每个丑数乘以2，在乘以2的时候，能够得到若干个小于或者等于M的结果。由于是按照顺序生成的，小于或者等于M的数肯定已经在丑数数组当中了，我们不需要再次考虑；当然还会得到若干大于M的结果，但是我们只需要第一个大于M的结果，因为我们希望丑数是按顺序排列的，所以其他更大的结果可以以后考虑。我们把得到的第一个乘以2以后得到的大于M的结果记为M2。同样，我们把已有的每一个丑数乘以3和5，能得到第一个大于M的结果M3和M5。那么M后面的那一个丑数应该是M2,M3和M5当中的最小值：Min(M2,M3,M5)。比如将丑数数组中的数字按从小到大乘以2，直到得到第一个大于M的数为止，那么应该是2*2=4<M，3*2=6>M，所以M2=6。同理，M3=6，M5=10。所以下一个丑数应该是6。
前面分析的时候，提到把已有的每个丑数分别都乘以2，3和5。事实上这不是必须的，因为已有的丑数是按顺序存放在数组中的，对乘以2而言，肯定存在某一个丑数T2，排在她之前的每一个丑数乘以2得到的结果都会小于等于(<=)已有最大的丑数，在它之后的每一个丑数乘以2得到的结果都会大于已有的最大丑数。因此我们只需要记下这个丑数的位置，同时每次生成新的丑数的时候去更新这个T2。对于乘以3和5，同样存在这样的T3和T5。
代码示例
View Code
注意点：在程序最后有delete[] pUglyNumbers;这是因为动态数组与数组变量不同，动态分配的数组将一直存在，直到程序显式释放它为止。普通的数组变量，只要出了数组的作用于，其内存会自动释放。c++提供delete []表达式释放指针所指向的数组空间
本文转自xwdreamer博客园博客，原文链接：http://www.cnblogs.com/xwdreamer/archive/2012/09/25/2701185.html，如需转载请自行联系原作者
