[264][中等][动态规划][三指针][堆] 丑数 II

题目描述

264. 丑数 II 剑指 Offer 49. 丑数

编写一个程序，找出第 n 个丑数。

丑数就是质因数只包含 2, 3, 5 的正整数。

示例:

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

说明:

• 1 是丑数。

• n 不超过1690。

解题思路

丑数 II

对于很多限制了数值范围或数量大小的数学题目, 常常先将范围内所有的结果计算出来, 缓存起来, 之后对于每一个用例, 直接查询答案即可.

由于本题中指定查询的丑数数量不大于1690, 因此首先计算出来这1690个丑数是什么, 然后直接返回对应位置的数值即可.

三指针+动态规划

本题的动态规划的形式有些特别, 可以把最终丑数的列表作为状态, 即第$i$个丑数是什么. 状态转移方程也需要借助三指针才能给出.

从1开始, 我们不断地乘上2, 3, 5, 这样得到数, 它的因子中肯定只有2, 3, 5这三个正整数, 剩下的就是控制顺序, 依次得到递增的丑数, 保证顺序的排列.

使用三个指针$i_2$, $i_3$, $i_5$, 指向已有的丑数列表中的位置, 该位置乘以这个指针代表的因子, 就得到了新的丑数. 对于新的丑数, 一定是前面比较小的丑数乘以三个因子得到的, 我们选取$2 \times nums[i_2]$, $3 \times nums[i_3]$, $5 \times nums[i_5]$中最小的丑数添加到丑数列表中, 作为新的丑数, 并将对应因子的指针前进一位.

状态转移方程可以记为:

$nums[j] = \min(2 \times nums[i_2], 3 \times nums[i_3], 5 \times nums[i_5])$

可以看到$j$和$i_*$, 两个下标虽然作用于同一个数组, 但意义不同, 这点是需要注意的.

为什么新的丑数一定在$2 \times nums[i_2]$, $3 \times nums[i_3]$, $5 \times nums[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]

相关题目

• [313][中等][堆] 超级丑数