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

⭐️前面的话⭐️

大家好!本篇文章将介绍力扣[剑指offer]题解,展示代码语言暂时为:C与Java。(后续会更新C++代码)

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

导航小助手

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

⭐️剑指 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。
来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/chou-shu-lcof/

解题思路

该题定义了丑数首项为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 nanbnc,分别对应丑数第 a , b , c a,b,c abc项,其中 a , b , c < n a,b,c<n a,b,c<n
则:
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<n

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

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

源代码

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];
    }
}

总结

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

觉得文章写得不错的老铁们,点赞评论关注走一波!谢谢啦!

    原文作者:未见花闻
    原文地址: https://blog.csdn.net/m0_59139260/article/details/121022143
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞