题目描述
编写一个程序，找出第 n 个丑数。
丑数就是质因数只包含 2, 3, 5 的正整数。
示例:
复制 输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。 说明:
解题思路
对于很多限制了数值范围 或数量大小 的数学题目, 常常先将范围内所有的结果计算出来, 缓存起来, 之后对于每一个用例, 直接查询答案即可.
由于本题中指定查询的丑数数量不大于1690, 因此首先计算出来这1690个丑数是什么, 然后直接返回对应位置的数值即可.
三指针+动态规划
本题的动态规划的形式有些特别, 可以把最终丑数的列表作为状态, 即第i i i 三指针 才能给出.
从1开始, 我们不断地乘上2, 3, 5, 这样得到数, 它的因子中肯定只有2, 3, 5这三个正整数, 剩下的就是控制顺序, 依次得到递增的丑数, 保证顺序的排列.
使用三个指针i 2 i_2 i 2 i 3 i_3 i 3 i 5 i_5 i 5 2 × n u m s [ i 2 ] 2 \times nums[i_2] 2 × n u m s [ i 2 ] 3 × n u m s [ i 3 ] 3 \times nums[i_3] 3 × n u m s [ i 3 ] 5 × n u m s [ i 5 ] 5 \times nums[i_5] 5 × n u m s [ i 5 ]
状态转移方程可以记为:
n u m s [ j ] = min ( 2 × n u m s [ i 2 ] , 3 × n u m s [ i 3 ] , 5 × n u m s [ i 5 ] ) nums[j] = \min(2 \times nums[i_2], 3 \times nums[i_3], 5 \times nums[i_5]) n u m s [ j ] = min ( 2 × n u m s [ i 2 ] , 3 × n u m s [ i 3 ] , 5 × n u m s [ i 5 ])
可以看到j j j i ∗ i_* i ∗
为什么新的丑数一定在2 × n u m s [ i 2 ] 2 \times nums[i_2] 2 × n u m s [ i 2 ] 3 × n u m s [ i 3 ] 3 \times nums[i_3] 3 × n u m s [ i 3 ] 5 × n u m s [ i 5 ] 5 \times nums[i_5] 5 × n u m s [ i 5 ]
复制 class Ugly:
def __init__(self):
self.cache = [1]
p2, p3, p5 = 0, 0, 0
for i in range(1690):
res2, res3, res5 = self.cache[p2] * 2, self.cache[p3] * 3, self.cache[p5] * 5
new_number = min([res2, res3, res5])
self.cache.append(new_number)
p2 = p2 + 1 if new_number == res2 else p2
p3 = p3 + 1 if new_number == res3 else p3
p5 = p5 + 1 if new_number == res5 else p5
class Solution:
ugly = Ugly()
def nthUglyNumber(self, n: int) -> int:
return self.ugly.cache[n - 1] 堆
堆的方法与上面三指针的方法在思路上类似, 都是不断的乘上2, 3, 5, 但控制下一个丑数的任务简化了, 由三指针交给了擅长存储和排序的堆这种数据结构. 将所有计算得到的丑数都放入堆中, 这里使用最小堆. 每次取堆顶的元素加入到丑数列表中, 这个数肯定是当前未加入到丑数列表中的最小数.
需要注意堆中数字重复的问题, 为此需要额外使用一个哈希表来存储已经在列表中的丑数.
复制 class Ugly:
def __init__(self):
self.cache = []
heap = [1]
heapq.heapify(heap)
seen = set([1])
for _ in range(1690):
t_ugly = heapq.heappop(heap)
self.cache.append(t_ugly)
for i in [2, 3, 5]:
new_ugly = t_ugly * i
if new_ugly not in seen:
heapq.heappush(heap, new_ugly)
seen.add(new_ugly)
class Solution:
ugly = Ugly()
def nthUglyNumber(self, n: int) -> int:
return self.ugly.cache[n - 1] 相关题目