题解 | #丑数#

算法思想一：优先队列

解题思路：

采用一个简单的解法是使用优先队列：
1、起始先将最小丑数 1 放入队列
2、每次从队列取出最小值 x，然后将 x 所对应的丑数 2x、3x 和 5x 进行入队。
3、对步骤 2 循环多次，第 n 次出队的值即是答案。
注：为了防止同一丑数多次进队，需要使用数据结构 Set（explored） 来记录入过队列的丑数

代码展示：

Python版本

# -*- coding:utf-8 -*-
import heapq
class Solution:
    def GetUglyNumber_Solution(self, index):
        # write code here
        # 丑数质因子
        nums = [2,3,5]
        # set 列表
        explored = {1}
        pq = [1]
        for i in range(1, index+1):
            x = heapq.heappop(pq)
            if i == index:
                return x
            # 分别将x与质因子计算 并添加到 explored 中
            for num in nums:
                t = num * x
                # 用 explored 记录进入队列的丑数
                if t not in explored:
                    explored.add(t)
                    heapq.heappush(pq,t)
        return 0

复杂度分析

时间复杂度：从优先队列中取最小值为 O(1)，往优先队列中添加元素复杂度为 ，算法需要循环n次。整体复杂度为 。

空间复杂的：队列和set列表的存储空间

算法思想二：动态规划

解题思路：

方法一使用优先队列，会预先存储较多的丑数计算复杂，导致复杂度较高，可以使用动态规划的方法进行优化。
1、定义数组 dp，其中 dp[i] 表示第 i 个丑数，第 n 个丑数即为 dp[n]。由于最小的丑数是 1，因此 dp[1]=1。 特殊情况， n = 0, 直接返回0
2、定义三个指针 p2,p3,p5，表示下一个丑数是当前指针指向的丑数乘以对应的质因数。初始时，三个指针的值都是 1。
3、当 2≤i≤n 时，令 ，然后分别比较 和 ,, 是否相等，如果相等则将对应的指针加 1。
4、循环结束返回

图解：

代码展示：

JAVA版本

public class Solution {
    public int GetUglyNumber_Solution(int index) {
        // 特殊情况
        if (index <= 0){
            return 0;
        }
        // dp数组并初始化
        int[] dp = new int[index + 1];
        dp[1] = 1;
        // 三指针
        int p2 = 1, p3 = 1, p5 = 1;
        for (int i = 2; i <= index; i++) {
            // 分别计算三指针与质因子的乘积，选择最小值
            int num2 = dp[p2] * 2, num3 = dp[p3] * 3, num5 = dp[p5] * 5;
            dp[i] = Math.min(Math.min(num2, num3), num5);
            // 判断是哪个指针与质因子的乘积，指标前进
            if (dp[i] == num2) {
                p2++;
            }
            if (dp[i] == num3) {
                p3++;
            }
            if (dp[i] == num5) {
                p5++;
            }
        }
        // 返回dp数组最后一个元素
        return dp[index];
    }
}

复杂度分析

时间复杂度：。需要计算数组dp 中的 n 个元素，每个元素的计算都可以在 O(1) 的时间内完成。
空间复杂度：。空间复杂度主要取决于数组 dp 的大小。