剑指offer系列——剑指 Offer 49. 丑数

⭐️前面的话⭐️

大家好！本篇文章将介绍力扣[剑指offer]题解，展示代码语言暂时为：C与Java。（后续会更新C++代码）

博客主页：未见花闻的博客主页
欢迎关注点赞收藏⭐️留言
本文由未见花闻原创，CSDN首发！
首发时间：2021年10月28日
✉️坚持和努力一定能换来诗与远方！
刷题推荐书籍：《剑指offer第1版》，《剑指offer第2版》
参考在线编程网站：牛客网力扣
作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！
博主的码云gitee，平常博主写的程序代码都在里面。

• ⭐️剑指 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整除）
那么丑数一定是前面丑数某一项乘以质因子的数集中的最小值，因为有三个质因子，所以该数集有三个元素。
不妨设所求丑数 u g l y [ n ] ugly[n] ugly[n]的项数为 n n n，数集中三个数分别为 n a ， n b ， n c na，nb，nc na，nb，nc，分别对应丑数第 a ， b ， c a，b，c a，b，c项，其中 a , b , c < n a,b,c 则：
u g l y [ n ] = m i n { n a , n b , n c } ugly[n] = min{na, nb, nc} ugly[n]=min{na,nb,nc}
{ n a = u g l y [ a ] ∗ 2 n b = u g l y [ b ] ∗ 3 n c = u g l y [ c ] ∗ 5 , a , b , c < n left{ begin{array}{c} na = ugly[a] ∗ 2 \ nb = ugly[b] ∗ 3 \ nc = ugly[c] ∗ 5 end{array} right. ,a,b,c < n ⎩⎨⎧​na=ugly[a]∗2nb=ugly[b]∗3nc=ugly[c]∗5​,a,b,c

取得数集中最小值后，使最小值对应的项数加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];
    }
}

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