Python面试宝典第48题：找丑数
题目
我们把只包含质因子2、3和5的数称作丑数（Ugly Number）。比如：6、8都是丑数，但14不是，因为它包含质因子7。习惯上，我们把1当做是第一个丑数。求按从小到大的顺序的第n个丑数。
示例 1：
输入：5
输出：5示例 2：
输入：7
输出：8
暴力法
本题最直观的解法是使用暴力法，即从1开始逐个检查每个自然数是否为丑数，直到找到第n个丑数为止。使用暴力法求解本题的主要步骤如下。
1、定义一个函数，用于判断一个数是否为丑数。
2、从1开始遍历每一个数，对每个数调用该函数。
3、计数器记录已经找到的丑数的数量，当计数器达到n时，返回当前检查的数作为第n个丑数。
根据上面的算法步骤，我们可以得出下面的示例代码。
def is_ugly_number(num):
if num <= 0:
return False
for factor in [2, 3, 5]:
while num % factor == 0:
num //= factor
return num == 1
def find_ugly_numbers_by_brute_force(n):
count = 0
num = 1
while True:
if is_ugly_number(num):
count += 1
if count == n:
return num
num += 1
print(find_ugly_numbers_by_brute_force(5))
print(find_ugly_numbers_by_brute_force(7))优先队列法
优先队列法利用了最小堆的数据结构来保持未处理的丑数候选，其基本思想为：初始时，我们将1加入到优先队列中，因为1是最小的丑数；之后，每次从队列中取出最小的元素，并将其与2、3、5相乘后再次加入队列中。为了避免重复加入相同的丑数，我们需要记录之前加入队列的最大值，并确保不加入小于等于该最大值的数。使用优先队列法求解本题的主要步骤如下。
1、初始化堆和已知丑数。
（1）创建一个最小堆heap，并向其中添加第一个丑数1。
（2）创建一个集合seen，用于存储已经发现的丑数，以防止重复计算。
（3）设置变量last_ugly为 1，这代表最后加入的丑数。
（4）设置计数器count为 1，用来跟踪已经找到的丑数的数量。
2、循环直到找到第n个丑数，并执行以下操作。
（1）每次循环从堆中弹出最小的丑数current，并使用三个质因数（2、3、5）分别乘以current来生成新的丑数。
（2）对于每个新生成的丑数new_ugly，检查它是否已经被计算过，即是否存在于seen集合中。
（3）如果new_ugly还未被计算过，则将其添加到seen集合中，并将其推入堆heap中。
3、更新最后加入的丑数。
（1）如果弹出的丑数current不等于last_ugly，这意味着我们找到了一个新的丑数。
（2）更新last_ugly为current，并将count加一。
（3）当count达到n时，循环结束，此时last_ugly即为第n个丑数。
4、返回last_ugly作为第n个丑数。
根据上面的算法步骤，我们可以得出下面的示例代码。
import heapq
def find_ugly_numbers_by_priority_queue(n):
# 初始化最小堆
heap = [1]
# 记录最后一个加入堆的丑数
last_ugly = 1
# 已找到的丑数数量
count = 1
# 使用集合来去重
seen = set([1])
while count < n:
# 弹出当前最小的丑数
current = heapq.heappop(heap)
# 生成新的丑数并加入堆中
for factor in [2, 3, 5]:
new_ugly = current * factor
# 如果新生成的丑数还没有被加入过，则加入堆中
if new_ugly not in seen:
seen.add(new_ugly)
heapq.heappush(heap, new_ugly)
# 只有在当前丑数不等于最后一个加入的丑数时，才进行下一步操作
if current != last_ugly:
last_ugly = current
count += 1
# 最后一个加入的丑数就是第n个丑数
return last_ugly
print(find_ugly_numbers_by_priority_queue(5))
print(find_ugly_numbers_by_priority_queue(7))动态规划法
使用动态规划法的关键是：定义状态转移方程。假设dp[i]表示第i个丑数，则本题的状态转移方程为：dp[i] = min(2 * dp[j], 3 * dp[k], 5 * dp[l])。其中，j、k、l分别表示最近乘以2、3、5得到dp[i]的索引。边界条件为dp[1] = 1，因为1是最小的丑数。使用动态规划法求解本题的主要步骤如下。
1、初始化数组dp，长度为n + 1，其中dp[1] = 1。
2、定义三个指针j、k、l，初始值均为1。
3、对于每个i（从2到n），进行以下操作。
（1）计算dp[i]的值，它是2 * dp[j]、3 * dp[k]、5 * dp[l]中的最小值。
（2）如果dp[i]等于2 * dp[j]，则j加1。
（3）如果dp[i]等于3 * dp[k]，则k加1。
（4）如果dp[i]等于5 * dp[l]，则l加1。
4、当i达到n时，dp[n]就是第n个丑数。
根据上面的算法步骤，我们可以得出下面的示例代码。
def find_ugly_numbers_by_dp(n):
if n == 1:
return 1
# 初始化dp数组
dp = [0] * (n + 1)
dp[1] = 1
j, k, l = 1, 1, 1
for i in range(2, n + 1):
# 计算下一个丑数
dp[i] = min(2 * dp[j], 3 * dp[k], 5 * dp[l])
# 更新指针
if dp[i] == 2 * dp[j]:
j += 1
if dp[i] == 3 * dp[k]:
k += 1
if dp[i] == 5 * dp[l]:
l += 1
return dp[n]
print(find_ugly_numbers_by_dp(5))
print(find_ugly_numbers_by_dp(7))总结
暴力法的实现较为简单，但效率低下，尤其是在n较大的时候。最坏情况下，需要检查所有的数直到找到第n个丑数。假设第n个丑数是u(n)，则暴力法的时间复杂度为O(u(n))。其空间复杂度为O(1)，只需要常数级别的额外空间。
使用优先队列法时，插入和删除操作的时间复杂度为O(logu(n))，且需要做n次这样的操作，故总的时间复杂度为O(n*logu(n))。堆的大小最多为u(n)，故总的空间复杂度为O(u(n))。与暴力法相比，优先队列法的效率更高，但可能带来较多的空间消耗。
使用动态规划法时，每个数只被访问一次，故时间复杂度为O(n)。其空间复杂度也为O(n)，因为仅需要一个长度为n的数组来存储结果。动态规划法在时间和空间上都较为平衡，故实际应用中，通常倾向于使用动态规划法来解决这类问题。