⭐️前面的话⭐️

大家好！博主开辟了一个新的专栏——剑指offer，我要开始刷题了！这个专栏会介绍《剑指offer》书上所有的面试编程题。并且会分享一些我的刷题心得。由于博主水平有限，如有错误，欢迎指正，如果有更好的解题思路和算法可以分享给博主哦！一起加油！一起努力！

📒博客主页：未见花闻的博客主页
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
📌本文由未见花闻原创！
📆华为云首发时间：🌴2022年4月30日🌴
✉️坚持和努力一定能换来诗与远方！
💭参考书籍：📚《C语言程序设计》📚《剑指offer》
💬参考在线编程网站：🌐牛客网🌐力扣
博主的码云gitee，平常博主写的程序代码都在里面。
博主的github，平常博主写的程序代码都在里面。
🍭作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！

⭐️剑指 Offer 49. 丑数⭐️

🔐题目详情

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

示例：

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

提示：

1. 1 是丑数。
2. n 不超过1690。

💡解题思路

该题定义了丑数首项为1，并且只包含质因子 2、3 和 5（除了1以外，只能被2,3,5整除）
那么丑数一定是前面丑数某一项乘以质因子的数集中的最小值，因为有三个质因子，所以该数集有三个元素。
不妨设所求丑数 $ugly[n]$的项数为 $n$，数集中三个数分别为 $na，nb，nc$，分别对应丑数第 $a，b，c$项，其中 $a,b,c<n$。
则：

$$ugly[n] = min\{na, nb, nc\}$$

$$\left\{ \begin{array}{c} na = ugly[a] ∗ 2 \\ nb = ugly[b] ∗ 3 \\ nc = ugly[c] ∗ 5 \end{array} \right. ,a,b,c < n$$

取得数集中最小值后，使最小值对应的项数加1，比如na最小，则a++。如果存在多个最小值，每个最小值对应的项数都需要加1，,最后按照同样的方式求丑数下一项。

🔑源代码

C语言：

int min(int x, int y, int z)
{
    int m = 0;
    m = x < y ? x : y;
    m = m < z ? m : z;
    return m;
}
int nthUglyNumber(int n){
    int a = 0;
    int b = 0;
    int c = 0;
    int* ugly = (int*)malloc(sizeof(int) * n);
    int i = 0;
    ugly[0] = 1;
    for (i = 1; i < n; i++) 
    {
        int na = ugly[a] * 2;
        int nb = ugly[b] * 3;
        int nc = ugly[c] * 5;
        ugly[i] = min(na, nb, nc);
        if (ugly[i] == na)
            a++;
        if (ugly[i] == nb)
            b++;
        if (ugly[i] == nc)
            c++;
    }
    return ugly[n - 1];
}

Java语言：

class Solution {
    public int nthUglyNumber(int n) {
        int a = 0;
        int b = 0;
        int c = 0;
        int[] ugly = new int[n];
        int i = 0;
        ugly[0] = 1;
        for (i = 1; i < n; i++) {
            int na = ugly[a] * 2;
            int nb = ugly[b] * 3;
            int nc = ugly[c] * 5;

            int min = Math.min(na, nb);
            ugly[i] = Math.min(min, nc);

            if (ugly[i] == na) a++;
            if (ugly[i] == nb) b++;
            if (ugly[i] == nc) c++;
        }
        return ugly[n - 1];
    }
}

🌱总结

对于丑数或类似丑数的问题，最重要的是想出其递推公式，该题是依据丑数的后一项一定在前面某项乘以质因子所得的数集中，其最小值即是这一项。