0264 - Ugly Number II
题干
An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.
Given an integer n, return the nth ugly number.
破题
Medium 题目通常比 Hard 要棘手，因为干扰项多，很容易误入歧途，而 Hard 题目反而思路明确。
轮筛陷阱
这个题真是“坑”我不浅，首先 “ prime factors ” 和 Top 3 个质数 2, 3, 5 直接把我引到了“轮筛”这个概念里1，然后发现 轮筛 wiki 里有些概念讲得一带而过、很不清楚2，于是去查一些介绍质数筛子的教学材料，了解了一些质数筛子，但是轮筛还是不知道，又追到了 Pritchard 的原始论文，最后把他 80s-90s 所有质数筛子论文都看完了，内容详见 质数基础、 质数筛子 和 质数筛子拓展 ，回来发现本题和轮筛、和质数筛子、甚至和质数本身就没什么关系，真是一种幽默了。
GPF 陷阱
虽然但是， 可以发现丑数并不是按照 2, 3, 5 的某个固定顺序增长，感觉需要对既往丑数进行一个 $\log n$ 级别的回溯，才能准确找到大小顺序排在下一个的丑数。
这好像暗示可以计算每个数的最大质因子，这样快速检查一个数是否是符合条件（最大质因子（GPF） $\leqslant 5$）的丑数，而 GPF 增量筛算法恰好提供了一个 $O(n)$ 时间复杂度下计算 $\text{gpf}$ 数组的方法，看起来是个思路。
但问题是丑数增长是指数级的，在计算到需求的第 1680 个丑数前，且不说超时的问题，光内存就已经被消耗完了。
解① 堆：
找不到固定的变化规律，也应用不了既有算法，只能从头开始考虑，按照规律上讲，对于无法直接解决的问题，应该从答案入手、寻找规律，反推过程。这也是诱导推理或者动态规划思想的核心思路。
那么回到这个题目，$n$ th 丑数应该也是由某 $i$ th 丑数 x2, x3, x5 得到，而显然 $i \lt n$，也就是这个丑数是之前计算过的。
那么似乎为每个丑数 $a$ 计算 $2a$ , $3a$ , $5a$ 三个数，把它们加入候选集里，那么下一个丑数就可以在这个候选集里搜索，这是一个线性的复杂度，而选取其中的最小值，可以使用小顶堆，这就可以解决问题。
注意这样计算的候选项会有重复值。
N = 1690
def gen_ugly_numbers(n: int) -> list[int]:
""" n >= 1 """
ugly_numbers = [1]
probheap = []
while len(ugly_numbers) < n:
last = ugly_numbers[-1]
cur = heappushpop(probheap, last * 2)
while cur == last:
cur = heappop(probheap)
heappush(probheap, last * 3)
heappush(probheap, last * 5)
ugly_numbers.append(cur)
return ugly_numbers
UGLY_NUMBERS = gen_ugly_numbers(N)
def solve(n: int) -> int:
return UGLY_NUMBERS[n - 1]
因为堆的维护需要 $O(n\log n)$ ，因此总的时间复杂度也降低到了 $O(n\log n)$ ，空间复杂度 $O(n)$ 。
时间性能 0 ms (beats 100%)，空间性能 16.8 MB (beats 11.8%)。
这个 0 ms 是因为缓存了全部结果，其他提交大家好像都是动态计算结果
解② DP：
经验上大多数能用优先级队列解决的题目，也可以使用 DP 在 $O(n)$ 时间复杂度上解决。
仔细考虑下其实根本不用保存所有的候选值，只需要追踪前三个最小的丑数，设为 $a_1\lt a_2\lt a_3$ ，使得 $a_i=\min\lbrace a_i\vert a_i\cdot T[i] \gt \text{last ugly number} \rbrace, T= \lbrace 2, 3, 5\rbrace $，当前的丑数就是 $\min \lbrace 5a_1,3a_2,2a_3\rbrace$ 。
如果某个候选值被发现为最小，那么把它作为丑数添加后，需要更新 $a_i=\min\lbrace u\vert u \gt a_i, u\in \text{ugly nmubers} \rbrace$ 。
同样地，三个候选值 $5a_1,3a_2,2a_3$ 可能产生相同的值，需要全部检查一遍
N = 1690
def gen_ugly_numbers(n: int) -> list[int]:
""" n >= 1 """
ugly_numbers = [1]
i_m5 = i_m3 = i_m2 = 0
nxt_m2 = 2
nxt_m3 = 3
nxt_m5 = 5
while len(ugly_numbers) < n:
cur = min(nxt_m2, nxt_m3, nxt_m5)
ugly_numbers.append(cur)
if cur == nxt_m2:
i_m2 += 1
nxt_m2 = ugly_numbers[i_m2] * 2
if cur == nxt_m3:
i_m3 += 1
nxt_m3 = ugly_numbers[i_m3] * 3
if cur == nxt_m5:
i_m5 += 1
nxt_m5 = ugly_numbers[i_m5] * 5
return ugly_numbers
UGLY_NUMBERS = gen_ugly_numbers(N)
def solve(n: int) -> int:
return UGLY_NUMBERS[n - 1]
时间复杂度 $O(n)$ ，空间复杂度 $O(1)$ 。
时间性能：0 ms (beats 100%)，空间性能：16.59 MB (beats 80.55%)。
注解
