题⽬描述

把只包含质因⼦ 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 minHeap = new PriorityQueue();
        Set seen = new HashSet(); // 用于去重
        minHeap.offer(1L);
        seen.add(1L);
        
        long currentUgly = 1;
        int[] factors = {2, 3, 5};
        
        for (int i = 0; i 

• 时间复杂度​：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 

• 时间复杂度​：​O(n)​。只需一次循环即可计算出第n个丑数。
• ​空间复杂度​：​O(n)​。需要一个长度为n的数组来存储丑数序列。

本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top