【LeetCode】263.丑数 & 264. 丑数 II
I. 263. 丑数（是否为丑数）
一、题目描述
编写一个程序判断给定的数是否为丑数。
丑数就是只包含质因数 2, 3, 5 的正整数。
示例 1:
输入: 6
输出: true
解释: 6 = 2 × 3
示例 2:
输入: 8
输出: true
解释: 8 = 2 × 2 × 2
示例 3:
输入: 14
输出: false
解释: 14 不是丑数，因为它包含了另外一个质因数 7。
说明：
- 1 是丑数。
- 输入不会超过 32 位有符号整数的范围:
。
二、解题思路 & 代码
2.1 循环迭代
class Solution:
def isUgly(self, num: int) -> bool:
if(num==0):
return False
if(num==1):
return True
while(num%2==0):
num //=2
while(num%3==0):
num //=3
while(num%5==0):
num //=5
return num==1
2.2 递归
class Solution:
def isUgly(self, num: int) -> bool:
if(num==0):
return False
if(num==1):
return True
if(num%2==0):
return self.isUgly(num // 2)
if(num%3==0):
return self.isUgly(num // 3)
if(num%5==0):
return self.isUgly(num // 5)
return False
======================================================
II. 264. 丑数（找第 
一、题目描述
写一个程序，找出第 n 个丑数。
丑数就是质因数只包含 2, 3, 5 的正整数。
示例:
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:
二、解题思路 & 代码
2.1 动态规划
表示第 i 个丑数
前面的每一个数（状态）都可以乘上 2, 3, 5 来形成一个新的状态
创建 3 个指针 p2、p3、p5，分别表示这 3 个质数因子此时应该乘上第几个状态。
p2、p3、p5 的含义
实际上 
的含义是有资格同 
这里资格指的是：如果一个丑数 
通过乘以 可以得到下一个丑数，那么这个丑数 就永远失去了同 相乘的资格（没有必要再乘了），我们把 
让
举例说明：
- 一开始，丑数只有{1}，1可以同 2 、3 、5 相乘，取最小的 1 × 2 = 2 添加到丑数序列中。
- 现在丑数中有 {1，2} ，在上一步中，1 已经同 2 相乘过了，所以今后没必要再比较 1 × 2 了，我们说 1 失去了同 2 相乘的资格。
- 现在 1 有与 3、5 相乘的资格，2 有与 2、3、5 相乘的资格，但是 2 × 3 和 2 × 5 是没必要比较的，因为有比它更小的 1 可以同 3、5 相乘，所以我们只需要比较 1 × 3 、1 × 5 、 2 × 2 。
依此类推，每次我们都分别比较有资格同 2、3、5 相乘的最小丑数，选择最小的那个作为下一个丑数，假设选择到的这个丑数是同 i（ i = 2、3、5）相乘得到的，所以它失去了同 i 相乘的资格，把对应的 pi++ ，让 pi 指向下一个丑数即可。
class Solution:
def nthUglyNumber(self, n: int) -> int:
if( n < 1):
return 0
p2 = 0
p3 = 0
p5 = 0
dp = [0] * n
dp[0] = 1
for i in range(1, n):
# 比较此时可能的状态，取最小的那个
dp[i] = min(dp[p2] * 2, min(dp[p3] * 3, dp[p5] * 5))
# 更新指向
# 注意这里不能只更新一个指针
# 比如 6，可以由 2 * 2 * 2 形成，也可以由 2 * 3 组成
if( dp[i] == dp[p2] * 2): p2 += 1
if( dp[i] == dp[p3] * 3): p3 += 1
if( dp[i] == dp[p5] * 5): p5 += 1
return dp[n - 1]
复杂度分析
- 时间复杂度： O(n)。生成一个丑数只需常量时间，所以生成n个丑数需要 O(n)。
- 空间复杂度：O(n)。dp数组的长度为n。
参考：
- 字节跳动面到这道题，有的读者一脸懵逼，有的读者笑嘻嘻
2.2 优先队列(小顶堆)
利用优先队列有自动排序的功能
生成丑数的规律：如果已知丑数 ugly ，那么 ugly * 2，ugly * 3 和 ugly * 5 也都是丑数。
既然求第n小的丑数，可以采用最小堆来解决。每次弹出堆中最小的丑数，然后检查它分别乘以2、3和 5后的数是否生成过，如果是第一次生成，那么就放入堆中。第n个弹出的数即为第n小的丑数。
具体：每次取出队头元素，存入队头元素 *2、队头元素 *3、队头元素 *5 但注意，像12这个元素，可由 4 乘3得到，也可由6乘2得到，所以要注意去重
########################## 比较慢 ################################
# class Solution:
# def nthUglyNumber(self, n: int) -> int:
# c = set()
# m = 1
# stack = [1]
# d = []
# while len(d) < n:
# m = min(stack)
# stack.remove(m)
# d.append(m)
# if m * 2 not in c:
# stack.append(m * 2)
# c.add(m * 2)
# if m * 3 not in c:
# stack.append(m * 3)
# c.add(m * 3)
# if m * 5 not in c:
# stack.append(m * 5)
# c.add(m * 5)
# return d[n - 1]
########################## 比较快 ################################
import heapq
class Solution:
def nthUglyNumber(self, n: int) -> int:
heap = []
heapq.heappush(heap, 1)
seen = set()
seen.add(1)
factors = [2, 3, 5]
curr_ugly = 1
for _ in range(n):
curr_ugly = heapq.heappop(heap)
for f in factors:
new_ugly = curr_ugly * f
if new_ugly not in seen:
seen.add(new_ugly)
heapq.heappush(heap, new_ugly)
return
复杂度分析
- 时间复杂度： O(nlog(n))。弹出每个最小值时，时间复杂度都为堆的高度，因此时间复杂度为O(nlog(n)) 。
- 空间复杂度： O(n)。遍历n个丑数，并将每个丑数乘以 2、3 和 5 的结果存入堆中。堆和哈希表的元素个数都不会超过 n * 3。
参考：
- LeetCode题解
