题⽬描述
把只包含质因⼦ 2 、 3 和 5 的数称作丑数（ Ugly Number ）。例如 6 、 8 都是丑数，但 14 不是，因为它包含质因⼦ 7 。 习惯上我们把 1 当做是第⼀个丑数。求按从⼩到⼤的顺序的第 N 个丑数。
如果 n = 9， 返回 10 。注意事项：我们可以认为 1 也是⼀个丑数。
输⼊：7 返回值：8
思路及解答
暴⼒破解
⾸先，我们想到的是暴⼒破解，从1开始遍历，每⼀个数，都不断地除以2,3,5，看最后的结果是不是等于1，如果等于1则说明这个数是丑数，否则不是丑数。
代码如下（这样的结果就是很⼤的数据就会时间超限，跑得很慢）：
时间复杂度：O(n log n)。isUglyNumber 函数的时间复杂度约为O(log n)，需要调用n次。
空间复杂度：O(1)。
最小堆（优先队列）法
利用最小堆（优先队列）来按序生成丑数。从1开始，每次取出当前最小丑数，将其乘以2、3、5的结果加入堆中（需去重），第n次取出的即为第n个丑数
时间复杂度：O(n log n)。每次堆操作（插入和取出）的时间复杂度为O(log k)，k为堆中元素数量，最多约为3n。
空间复杂度：O(n)。堆和集合最多需要存储O(n)个元素。
优化的动态规划（空间优化）（三指针法）（推荐）
我们知道所有的丑数都是由 2 , 3 , 5 不断相乘产⽣的，也就是说，丑数只由丑数来产⽣，不断地从前⾯的丑数中去产⽣新的丑数，直到第n个。⾸先定义了⼀个n个空间的⼀维数组，只把 num[0]=1，然后我们使⽤三指针法，也就是我们定义 3 个下标，分别是 num_2 , num_3 , num_5 ,这些下标⼀开始都指向数组的0号元素，也就是他们的值都为0。
意思是下⼀个丑数由数组中 第 num_2 的元素2， 和 第num_3的元素3， 第num_5的元素5，这三个数中最⼩的来产⽣，⼀旦确定是最⼩的，那么该下标就要往后⾯移动。
⽐如第⼆个数，第⼀次下标都在 0，我们找到 num[0]，然后⽤2,3,5分别乘以 num[0]，得到 2 , 3,5，发现2最⼩，那么 num[1] = 2，这时候 num_2 这个下标就要移动到1，⽽ num_3 , num_5 不变，还是0。
此时 num_2 = 1，num_3 = 0， num_5=0。第三个数将由 num[num_2] * 2 , num[num_3] * 3 , num[5] * 5 来产⽣，得到第三个数是num[2] = num[num_3] * 3 = 1 * 3 = 3，那么 num_3 这个下标就要后移到1。
此时 num_2 = 1，num_3 = 1， num_5 = 0。第四个数就由 num[num_2] * 2 , num[num_3] * 3 , num[num_5] * 5，发现 num[num_2] * 2 = =4 最⼩，所以第四个数num[3]就是4， num_2 这个下标⼜后移。
此时 num_2=2， num_3=1， num_5=0 …就这样不断地操作，得到最终的结果。
如果觉得这个不好理解，可以先看下一个版本的基础版的动态规划
那么值得注意的是，如果三个数⾥⾯有两个是⼀样的，也就是可能 num[num_2]*2 刚好就等于num[num_3]*3 ,那么我们就要 num_2， num_3 两个都下标都移动，所以不能使⽤ if-else，⽽是都使⽤ if 判断。代码如下：
时间复杂度：O(n)。只需一次循环即可计算出第n个丑数。
空间复杂度：O(n)。需要一个长度为n的数组来存储丑数序列。
基础版动态规划
状态定义：设 dp[i] 表示按从小到大的顺序排列的第 i + 1 个丑数（因为数组下标从 0 开始）。
初始状态：dp[0] = 1（1 是第一个丑数）。
转移方程：下一个丑数必然是由之前的某个丑数乘以 2、3 或 5 得到的。为了保证严格递增且不遗漏，我们取三个候选值中的最小值： dp[i] = min(dp[p2] * 2, dp[p3] * 3, dp[p5] * 5)
指针更新：如果当前算出的最小值等于某个候选值，就将对应的指针后移一位。注意必须使用独立的 if 判断，这样当多个指针产生相同的值（例如 2×3=6，2×3=6 且 3×2=6，3×2=6 ）时，所有相关指针都会移动，从而天然实现去重。
返回值：dp[n - 1]，即第 n 个丑数。