题⽬描述
把只包含质因⼦ 2 、 3 和 5 的数称作丑数（ Ugly Number ）。例如 6 、 8 都是丑数，但 14 不是，因为它包含质因⼦ 7 。 习惯上我们把 1 当做是第⼀个丑数。求按从⼩到⼤的顺序的第 N 个丑数。
如果 n = 9 ， 返回 10 。注意事项：我们可以认为 1 也是⼀个丑数。
输⼊：7
返回值：8
思路及解答
暴⼒破解
⾸先，我们想到的是暴⼒破解，从1开始遍历，每⼀个数，都不断地除以2,3,5，看最后的结果是不是等于1，如果等于1则说明这个数是丑数，否则不是丑数。
代码如下（这样的结果就是很⼤的数据就会时间超限，跑得很慢）：
public class Solution {public int nthUglyNumber(int n) {for(int i=1;;i++){if(isUglyNumber(i)==true)n--;if(n==0)return i;}}public boolean isUglyNumber(int num){while(num%2==0)num/=2;while(num%3==0)num/=3;while(num%5==0)num/=5;if(num==1)return true;elsereturn false;}}
- 时间复杂度：O(n log n)。isUglyNumber 函数的时间复杂度约为O(log n)，需要调用n次。
- 空间复杂度：O(1)。
最小堆（优先队列）法
利用最小堆（优先队列）来按序生成丑数。从1开始，每次取出当前最小丑数，将其乘以2、3、5的结果加入堆中（需去重），第n次取出的即为第n个丑数
public class Solution {public int nthUglyNumber(int n) {// 使用Long防止整数溢出PriorityQueue<Long> minHeap = new PriorityQueue<>();Set<Long> seen = new HashSet<>(); // 用于去重minHeap.offer(1L);seen.add(1L);long currentUgly = 1;int[] factors = {2, 3, 5};for (int i = 0; i < n; i++) {currentUgly = minHeap.poll();// 将当前丑数乘以2、3、5，并加入堆中（如果未见过）for (int factor : factors) {long newUgly = currentUgly * factor;if (seen.add(newUgly)) { // add方法在元素不存在时返回trueminHeap.offer(newUgly);}}}return (int) currentUgly;}
}
- 时间复杂度：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[1]*2 , num[0]*3 , num[0]*5 来产⽣，得到第三个数是3，那么 num_3 这个下标就要后移到1。
第四个数就由 num[1]*2 , num[1]*3 , num[0]*5 ，发现 num[1]*2=4 最⼩，所以第四个数就是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 判断。代码如下：
public class Solution {public int nthUglyNumber(int n) {if (n <= 0) return 0;int[] ugly = new int[n];ugly[0] = 1; // 第一个丑数是1int p2 = 0, p3 = 0, p5 = 0; // 初始化三个指针for (int i = 1; i < n; i++) {// 计算三个候选丑数int ugly2 = ugly[p2] * 2;int ugly3 = ugly[p3] * 3;int ugly5 = ugly[p5] * 5;// 选择最小的候选值作为下一个丑数int nextUgly = Math.min(ugly2, Math.min(ugly3, ugly5));ugly[i] = nextUgly;// 移动产生最小值的指针（注意不是else-if，因为可能多个指针产生相同值）if (nextUgly == ugly2) p2++;if (nextUgly == ugly3) p3++;if (nextUgly == ugly5) p5++;}return ugly[n - 1];}
}
- 时间复杂度：O(n)。只需一次循环即可计算出第n个丑数。
- 空间复杂度：O(n)。需要一个长度为n的数组来存储丑数序列。