剑指offer 丑数

浅浅的花香味﹌ 2022-05-21 05:19 392阅读 0赞

# 题目描述 #

把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

# 解题思路 #

丑数不难找，关键是如何让他们从小到大找到  
下一个丑数总是由以前的某个丑数乘以2或3或5得到，我们只要每次找到以前的丑数中的一些数，然后乘以2,3,5，将其中最小的那个加入集合，再重复以上过程，直到第N次  
因为总不能每次都从集合头开始尝试，我用i2,i3,i5记录上次乘以2,3,5的数字的下标，得到新的数字，记为num2,num3,num5，然后找最小的那个，并将那个所对应的下标++

![58756514.jpg][]

#include < vector > class Solution { 
        public: int getmin(int a, int b, int c) {
            int smaller = a < b ? a: b;
            return smaller < c ? smaller: c;
        }
        int GetUglyNumber_Solution(int index) {
            if (index == 0) {
                return 0;
            }
            vector < int > numbers;
            int currindex = 0;
            numbers.push_back(1);
            int i2 = 0;
            int i3 = 0;
            int i5 = 0;
            while (currindex < index) {
                int num2 = numbers[i2] * 2;
                int num3 = numbers[i3] * 3;
                int num5 = numbers[i5] * 5;
                int min = getmin(num2, num3, num5);
                numbers.push_back(min);
                if (min == num2) i2++;
                if (min == num3) i3++;
                if (min == num5) i5++;
                currindex++;
            }
            return numbers[index - 1];
        }
    };

[58756514.jpg]: http://oz9fdm91f.bkt.clouddn.com/18-6-30/58756514.jpg

发表评论取消回复

表情：

评论列表（有 0 条评论，392人围观）

还没有评论，来说两句吧...

相关阅读

相关剑指Offer：丑数

1. 题目描述输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组\{3，32，321\}，则打印出这三个数字能排成

灰太狼/ 2023年07月18日 14:06/ 0 赞/ 18 阅读

相关剑指Offer-丑数

转载地址：[https://www.jianshu.com/p/9598e96ea6b6][https_www.jianshu.com_p_9598e96ea6b6] 题目：

痛定思痛。/ 2022年05月23日 07:21/ 0 赞/ 204 阅读

相关剑指Offer | 丑数

做了个剑指Offer的题目目录，链接如下： [https://blog.csdn.net/mengmengdastyle/article/details/80317246]

超、凢脫俗/ 2022年05月23日 05:26/ 0 赞/ 170 阅读

相关剑指offer 丑数

题目描述把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。习惯上我们把1当做是第一个丑数。求按从小到大的

浅浅的花香味﹌/ 2022年05月21日 05:19/ 0 赞/ 393 阅读

相关剑指offer: 丑数

题目描述把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。习惯上我们把1当做是第一个丑数。求按从小到

青旅半醒/ 2022年02月23日 01:22/ 0 赞/ 194 阅读

相关剑指Offer-丑数

题目描述把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。习惯上我们把1当做是第一个丑数。求按从小到

朱雀/ 2022年02月19日 01:56/ 0 赞/ 202 阅读

相关剑指offer|丑数

【题目描述】把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。习惯上我们把1当做是第一个丑数。求按从小

小鱼儿/ 2022年01月28日 16:41/ 0 赞/ 241 阅读

相关剑指offer：丑数

题目描述：把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。习惯上我们把1当做是第一个丑数。求按从小到大

亦凉/ 2021年12月09日 01:09/ 0 赞/ 282 阅读

相关 [剑指offer]丑数

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个

妖狐艹你老母/ 2021年11月22日 15:22/ 0 赞/ 285 阅读

相关 [剑指offer]丑数

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个

﹏ヽ暗。殇╰゛Y/ 2021年11月17日 11:26/ 0 赞/ 284 阅读