题目(丑数)

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

算法思路一

逐个判断数是不是丑数，如果是丑数就计数，直到达到第 N 个丑数。而丑数是只含质因子 2，3，5的数。

算法思路二

算法实现二基于用前一个丑数求解下一个丑数的思想。即，对于一个有序的丑数数组，后面的丑数一定是前面的某个丑数乘以 2、3 或 5 的结果。
那么如何保证丑数数组有序呢？假设对于丑数 a，b，c(a,b,c 可相同)，下一个丑数可能为 2a、3b 或 5c 三种之一，那么我们就选取这三个数的最小丑数存入数组中，但是为了要继续更新下一个可能的丑数，我们必须记录这三种丑数对应的前一个丑数的位置(ps:每一种就是用前一个丑数乘以相应的质因子得到下一个丑数)，所以在我们将最小的那种丑数存入丑数数组时，还需要对那种丑数对应的指示器执行加 1 操作，即更新当前这种丑数的位置，以便继续求解下一个丑数。

算法实现一

算法实现二(优化版)

复杂度

算法思路一，尽管空间复杂度小，但由于需要对每个数判断丑数，因此浪费了很多时间再非丑数的判别上；而算法思路二，虽然额外建立了一个动态数组，但是它不需要对每个数判别丑数，大大提高了时间效率，也就是以空间换时间的解法。

参考

[1] <<剑指offer2>>
[2] 牛客网