leetcode264 丑数 II

给你一个整数 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 n
        dp = [0 for _ in range(n)]
        index = [0,0,0]
        for i in range(6):
            dp[i] = i+1
        factor = [2,3,5]
        for i in range(6,n):
            dp[i] = dp[i-1]*2
            for f in range(3):
                while(dp[index[f]]*factor[f] <= dp[i-1]):
                    index[f] += 1
                if index[f] < i:
                    dp[i] = min(dp[index[f]]*factor[f],dp[i])
        return dp[-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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

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 x
            for num in nums:
                t = num * x
                if t not in explored:
                    explored.add(t)
                    heapq.heappush(pq,t)
        return -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

时间复杂度：从优先队列中取最小值为 $O(1)$，往优先队列中添加元素复杂度为 $O(\log n)$。整体复杂度为$O(n\log 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）