剑指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则说明这个数是丑数，否则不是丑数。
代码如下（这样的结果就是很⼤的数据就会时间超限，跑得很慢）：
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;
else
return 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方法在元素不存在时返回true
minHeap.offer(newUgly);
}
}
}
return (int) currentUgly;
}
}
[*]时间复杂度：O(n log n)。每次堆操作（插入和取出）的时间复杂度为O(log k)，k为堆中元素数量，最多约为3n。
[*]空间复杂度：O(n)。堆和集合最多需要存储O(n)个元素。
动态规划（三指针法）（推荐）
我们知道所有的丑数都是由 2 , 3 , 5 不断相乘产⽣的，也就是说，丑数只由丑数来产⽣，不断地从前⾯的丑数中去产⽣新的丑数，直到第n个。⾸先定义了⼀个n个空间的⼀维数组，只把 num=1 ，然后我们使⽤三指针法，也就是我们定义 3 个下标，分别是 num_2 , num_3 , num_5 ,这些下标⼀开始都指向数组的0号元素，也就是他们的值都为0。
意思是下⼀个丑数由数组中 第 num_2 的元素2 ， 和 第num_3的元素3 ， 第num_5的元素5 ，这三个数中最⼩的来产⽣，⼀旦确定是最⼩的，那么该下标就要往后⾯移动。
⽐如第⼆个数，第⼀次下标都在 0，我们找到 num ，然后⽤2,3,5分别乘以 num ，得到 2 , 3,5，发现2最⼩，那么 num 就是2，这时候 num_2 这个下标就要移动到1，⽽ num_3 , num_5 不变，还是0。
第三个数将由 num*2 , num*3 , num*5 来产⽣，得到第三个数是3，那么 num_3 这个下标就要后移到1。
第四个数就由 num*2 , num*3 , num*5 ，发现 num*2=4 最⼩，所以第四个数就是4， num_2 这个下标⼜后移。
此时 num_2=2 ， num_3=1 ， num_5=0 ...就这样不断地操作，得到最终的结果。
那么值得注意的是，如果三个数⾥⾯有两个是⼀样的，也就是可能 num*2 刚好就等于num*3 ,那么我们就要 num_2 ， num_3 两个都下标都移动，所以不能使⽤ if-else ，⽽是都使⽤ if 判断。代码如下：
public class Solution { public int nthUglyNumber(int n) { if (n
页:
[1]