描述
设计一个算法，找出只含素因子2，3，5 的第 n 小的数。
符合条件的数如：1, 2, 3, 4, 5, 6, 8, 9, 10, 12...：
我们可以认为 1 也是一个丑数。
在线评测地址：领扣题库官网
样例1
输入：9
输出：10样例2
输入：1
输出：1解题思路1：最小堆
- 很容易想到的方法是：从1起检验每个数是否为丑数，直到找到n个丑数为止。但是随着n的增大，绝大部分数字都不是丑数，我们枚举的效率非常低。因此，换个角度思考，如果我们只生成丑数，且生成n个，这道题就迎刃而解。
- 不难发现生成丑数的规律：如果已知丑数ugly，那么ugly 2，ugly 3和ugly * 5也都是丑数。
- 既然求第n小的丑数，可以采用最小堆来解决。每次弹出堆中最小的丑数，然后检查它分别乘以2、3和 5后的数是否生成过，如果是第一次生成，那么就放入堆中。第n个弹出的数即为第n小的丑数。
算法流程
- 创建最小堆heap，哈希表 seen和质因数列表factors = [2, 3, 5]。heap用于存储已生成的丑数，弹出最小值；seen用于标记堆中出现过的元素，避免重复入堆。
- 初始化将1入堆，并添加到seen。
- 重复以下步骤n次： 弹出堆中最小的数字 curr_ugly。 对于factors中每个因数f，生成新的丑数new_ugly。若new_ugly不在seen中，则将其添加到heap中并更新seen。
- curr_ugly即为第n小的丑数，返回。
复杂度分析
- 时间复杂度：O(nlog(n))O(nlog(n))。弹出每个最小值时，时间复杂度都为堆的高度，因此时间复杂度为O(nlog(n))O(nlog(n))。
- 空间复杂度：O(n)O(n)。遍历n个丑数，并将每个丑数乘以2、3和5的结果存入堆中。堆和哈希表的元素个数都不会超过n * 3。
代码
import heapq
class Solution:
"""
@param n: An integer
@return: return a integer as description.
"""
def nthUglyNumber(self, n):
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 curr_ugly解题思路2：动态规划
- 在最小堆方法中，我们的思路是把当前丑数能生成的丑数都加入到堆中，然后再弹出最小值。如果我们能知道下一个最小的丑数，每次只生成最小的那个，就可以节省最小值查询的时间消耗。
- 采用动态规划的方法，用一个有序数组dp记录前n个丑数。三个指针l2，l3和l5指向dp中的元素，最小的丑数只可能出现在dp[l2]的2倍、dp[l3]的3倍和dp[l5]的5倍三者中间。通过移动三个指针，就能保证生成的丑数是有序的。
算法流程
- 初始化数组dp和三个指针l2、l3和l5。dp[0] = 1，表示最小的丑数为1。三个指针都指向dp[0]。
重复以下步骤n次，dp[i]表示第i + 1小的丑数：
- 比较2 dp[l2], 3 dp[l3], 5 * dp[l5]三者大小，令dp[i]为其中的最小值。
- 如果dp[i] == 2 * dp[l2]，l2指针后移一位。
- 如果dp[i] == 3 * dp[l3]，l3指针后移一位。
- 如果dp[i] == 2 * dp[l5]，l5指针后移一位。
- dp[n - 1]即为第n小的丑数，返回。
复杂度分析
- 时间复杂度：O(n)O(n)。生成一个丑数只需常量时间，所以生成n个丑数需要O(n)O(n)。
- 空间复杂度：O(n)O(n)。dp数组的长度为n。
代码
import heapq
class Solution:
"""
@param n: An integer
@return: return a integer as description.
"""
def nthUglyNumber(self, n):
dp = [0] * n
dp[0] = 1
l2, l3, l5 = 0, 0, 0
for i in range(1, n):
# 生成第i+1小的丑数
dp[i] = min(2 * dp[l2], 3 * dp[l3], 5 * dp[l5])
if dp[i] == 2 * dp[l2]:
l2 += 1
if dp[i] == 3 * dp[l3]:
l3 += 1
if dp[i] == 5 * dp[l5]:
l5 += 1
return dp[n - 1]更多题解参考：九章官网solution
