给你一个整数 n ，请你找出并返回第 n 个 丑数 。

丑数 就是只包含质因数 2、3 和/或 5 的正整数。

示例 1：

输入：n = 10
输出：12
解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。

示例 2：

输入：n = 1
输出：1
解释：1 通常被视为丑数。

本题我首先考虑的是用动态规划的方法进行求解，但是直接使用动态规划暴力求解的话计算量过大，会出现超时的情况。
因此我们需要结合三指针的方法进行化简
我自己写的代码如下所示

class Solution:def nthUglyNumber(self, n: int) -> int:if n <= 6: return ndp = [0 for _ in range(n)]index = [0,0,0]for i in range(6):dp[i] = i+1factor = [2,3,5]for i in range(6,n):dp[i] = dp[i-1]*2for f in range(3):while(dp[index[f]]*factor[f] <= dp[i-1]):index[f] += 1if index[f] < i:dp[i] = min(dp[index[f]]*factor[f],dp[i])return dp[-1]

首先使用一个字符串记录之前的丑数
接着使用三指针记录当前以2，3，5为因子的丑数的位置，因为我们的第n个丑数肯定是由之前某个丑数*2或3或5生成的。

当然评论区中有更为简单的表示方法，不需要对三个数都进行判断，代码如下所示

class Solution:def nthUglyNumber(self, n: int) -> int:if n <= 6: return ndp = [0 for _ in range(n)]index = [0,0,0]dp[0] = 1for i in range(1,n):a = dp[index[0]]*2b = dp[index[1]]*3c = dp[index[2]]*5m = min(a,b,c)if a == m:index[0] += 1if b == m:index[1] += 1if c == m:index[2] += 1dp[i] = mreturn dp[-1]

最后是采用更方便的数据结构的方法：优先队列（小根堆）
因为小根堆会自动排序，所以就方便了许多：

class Solution(object):def nthUglyNumber(self, n):""":type n: int:rtype: int"""nums = [2,3,5]explored = {1}pq = [1]for i in range(1, n+1):x = heapq.heappop(pq)if i == n:return xfor num in nums:t = num * xif t not in explored:explored.add(t)heapq.heappush(pq,t)return -1

时间复杂度：从优先队列中取最小值为 O(1)O(1)O(1)，往优先队列中添加元素复杂度为 O(log⁡n)O(\log{n})O(logn)。整体复杂度为O(nlog⁡n)O(n\log{n})O(nlogn)。
空间复杂度：O(n)O(n)O(n)。

作者：AC_OIer
链接：https://leetcode.cn/problems/ugly-number-ii/solution/gong-shui-san-xie-yi-ti-shuang-jie-you-x-3nvs/
来源：力扣（LeetCode）