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

2022 年 6 月 13 日
本文字数：1002 字
阅读完需：约 3 分钟

⭐️剑指 Offer 49. 丑数⭐️

🔐题目详情

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

示例：

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

复制代码

提示：

1 是丑数。
n 不超过 1690。

💡解题思路

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

u g l y [n] = m i n n a, n b, n 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];    }}

复制代码

🌱总结

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

发布于: 刚刚阅读数: 3

原文链接:【http://xie.infoq.cn/article/876768f59dcb309ca83e6235c】。文章转载请联系作者。

未见花闻

关注

还未添加个人签名 2021.11.15 加入

还未添加个人简介

发布

暂无评论

创作场景

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

⭐️剑指 Offer 49. 丑数⭐️

🔐题目详情

💡解题思路

🔑源代码

🌱总结

未见花闻

评论