【一刷《剑指Offer》】面试题 34：丑数

力扣对应题目链接：264. 丑数 II - 力扣（LeetCode）

牛客对应题目链接：丑数_牛客题霸_牛客网 (nowcoder.com)

一、《剑指Offer》对应内容

二、分析题目

根据题意，每个丑数都可以由其他较小的丑数通过乘以 2 或 3 或 5 得到。所以，我们可以考虑使用一个优先队列保存所有的丑数，每次取出最小的那个，然后乘以 2 , 3 , 5 后放回队列。然而，这样做会出现重复的丑数。例如：

初始化丑数列表 [1]
第一轮： 1 -> 2, 3, 5 ，丑数列表变为 [1, 2, 3, 5]
第二轮： 2 -> 4, 6, 10 ，丑数列表变为 [1, 2, 3, 4, 6, 10]
第三轮： 3 -> 6, 9, 15 ，出现重复的丑数 6

为了避免重复，我们可以用三个指针 p2、p3、p5 来分别表示下一个丑数是当前指针指向的丑数乘以 2、3、5。

利用三个指针生成丑数的算法流程：

• 初始化丑数列表 dp，首个丑数为 1 ，三个指针 p2、p3、p5 都指向首个丑数。
• 开启循环生成丑数：

1. 计算下一个丑数的候选集 dp[p2]*2、dp[p3]*3、dp[p5]*5 。
2. 选择丑数候选集中最小的那个作为下一个丑数，填入 dp。
3. 将被选中的丑数对应的指针向右移动一格。

• 返回 dp 的最后一个元素即可。

三、代码

//力扣
class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> dp(n+1);
        dp[1]=1;
        int p2=1, p3=1, p5=1;
        for(int i=2; i<=n; i++)
        {
            int num2=dp[p2]*2;
            int num3=dp[p3]*3;
            int num5=dp[p5]*5;
            dp[i]=min(num2, min(num3, num5));
            if(dp[i]==num2) p2++;
            if(dp[i]==num3) p3++;
            if(dp[i]==num5) p5++;
        }
        return dp[n];
    }
};

//牛客
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param index int整型 
     * @return int整型
     */
    int GetUglyNumber_Solution(int index) {
        if(index==0) return 0;
        vector<int> dp(index+1);
        dp[1]=1;
        int a=1, b=1, c=1;
        for(int i=2; i<=index; i++)
        {
            int x=dp[a]*2;
            int y=dp[b]*3;
            int z=dp[c]*5;
            dp[i]=min(x, min(y, z));
            if(dp[i]==x) a++;
            if(dp[i]==y) b++;
            if(dp[i]==z) c++;
        }
        return dp[index];
    }
};