原题目在这里，我懒得复制了直接放我自己得解法啦~

原题戳我~

解题思路 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] 

大佬有話說 (0)