剑指offer-33、丑数

题⽬描述

把只包含质因⼦ 2 、 3 和 5 的数称作丑数（ Ugly Number ）。例如 6 、 8 都是丑数，但 14 不是，因为它包含质因⼦ 7 。 习惯上我们把 1 当做是第⼀个丑数。求按从⼩到⼤的顺序的第 N 个丑数。
如果 n = 9 ， 返回 10 。注意事项：我们可以认为 1 也是⼀个丑数。
输⼊：7
返回值：8
思路及解答

暴⼒破解

⾸先，我们想到的是暴⼒破解，从1开始遍历，每⼀个数，都不断地除以2,3,5，看最后的结果是不是等于1，如果等于1则说明这个数是丑数，否则不是丑数。
代码如下（这样的结果就是很⼤的数据就会时间超限，跑得很慢）：

1. public class Solution {
3.         public int nthUglyNumber(int n) {
4.                 for(int i=1;;i++){
5.                         if(isUglyNumber(i)==true)
6.                                 n--;
7.                         if(n==0)
8.                                 return i;
9.                 }
10.         }
11.        
12.         public boolean isUglyNumber(int num){
13.                 while(num%2==0)
14.                         num/=2;
15.                 while(num%3==0)
16.                         num/=3;
17.                 while(num%5==0)
18.                         num/=5;
19.                 if(num==1)
20.                         return true;
21.                 else
22.                         return false;
23.         }
25. }

复制代码

• 时间复杂度​：O(n log n)。isUglyNumber 函数的时间复杂度约为O(log n)，需要调用n次。
  
• ​空间复杂度​：O(1)。
  

最小堆（优先队列）法

利用最小堆（优先队列）来按序生成丑数。从1开始，每次取出当前最小丑数，将其乘以2、3、5的结果加入堆中（需去重），第n次取出的即为第n个丑数

1. public class Solution {
2.     public int nthUglyNumber(int n) {
3.         // 使用Long防止整数溢出
4.         PriorityQueue<Long> minHeap = new PriorityQueue<>();
5.         Set<Long> seen = new HashSet<>(); // 用于去重
6.         minHeap.offer(1L);
7.         seen.add(1L);
8.         
9.         long currentUgly = 1;
10.         int[] factors = {2, 3, 5};
11.         
12.         for (int i = 0; i < n; i++) {
13.             currentUgly = minHeap.poll();
14.             // 将当前丑数乘以2、3、5，并加入堆中（如果未见过）
15.             for (int factor : factors) {
16.                 long newUgly = currentUgly * factor;
17.                 if (seen.add(newUgly)) { // add方法在元素不存在时返回true
18.                     minHeap.offer(newUgly);
19.                 }
20.             }
21.         }
22.         return (int) currentUgly;
23.     }
24. }

复制代码

• 时间复杂度​：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 判断。代码如下：
[code]public class Solution {    public int nthUglyNumber(int n) {        if (n