162-求第N个丑数的值

我会带着你远行 2022-10-24 13:27 152阅读 0赞

## 什么是丑数？ ##

把只包含质因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数，但7、14不是，因为它们包含质因子7。 习惯上我们把1当做是第一个丑数。

前20个丑数为:1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36

## 求第n个丑数是多少 ##

#include<iostream>
    #include<vector>
    #include<algorithm>
    using namespace std;
    int GetUglyNumber(int index)
    {
        
        //第N个丑数
        //丑数思想   2 3 5为因子    丑数j = 丑数i*(2或者3或者5得到)
        if (index < 7)
            return index;
        vector<int> ivec(index, 0);
        ivec[0] = 1;
        int t2 = 0, t3 = 0, t5 = 0;
        for (int i = 1; i < index; ++i)
        {
        
    		ivec[i] = min(min(ivec[t2] * 2, ivec[t3] * 3), ivec[t5] * 5);
            if (ivec[i] == ivec[t2] * 2)
                t2++;
            if (ivec[i] == ivec[t3] * 3)
                t3++;
            if (ivec[i] == ivec[t5] * 5)
                t5++;
        }
        return ivec[index - 1];
    }
    
    int main()
    {
        
    	cout<<GetUglyNumber(10)<<endl;
    	return 0;
    }

**运行截图如下**  
![在这里插入图片描述][20210129214740168.png_pic_center]

[20210129214740168.png_pic_center]: /images/20221024/ded2346b86624dc79d653baa61d535bf.png

发表评论取消回复

表情：

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

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

相关阅读

相关求N个数的最大值，最小值，和（C语言）

入格式第一行为整数 n，表示数的个数。第二行有 n 个数，为给定的 n 个数，每个数的绝对值都小于 10000。如输入： Entern:5 -159322 ...

末蓝、/ 2024年04月18日 14:54/ 0 赞/ 69 阅读

相关找到第n个数，

find the nth digit Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K

「爱情、让人受尽委屈。」/ 2024年02月18日 23:15/ 0 赞/ 7 阅读

相关 N33_丑数

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

た入场券/ 2023年08月17日 17:36/ 0 赞/ 71 阅读

相关求包含n个整数的数组A的第i小的数

题目：求包含n个整数的数组A的第i小的数。解法一：排序将数组A从小到大排序，之后第i个数即为所求。时间复杂度为O(n²) 解法二：维护一个长度为i

小鱼儿/ 2023年07月12日 14:21/ 0 赞/ 1 阅读

相关寻找第n个丑数

寻找第n个丑数应用案例案例分析丑数的概念过程分析代码实现应用案例编写一个程序，找出第n个丑

骑猪看日落/ 2023年07月10日 14:27/ 0 赞/ 3 阅读

相关 java n个数的和_Java如何求n个数字的和？

在Java编程中，如何求n个数字的和？以下示例演示了如何使用堆栈的概念来将n个自然数相加求和。 package com.yiibai; import java.io.IO

淡淡的烟草味﹌/ 2022年11月02日 13:16/ 0 赞/ 180 阅读

相关 162-求第N个丑数的值

什么是丑数？把只包含质因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数，但7、14不是，因为它们包含质因子7。习惯上我们把1当做是第一个丑数。

我会带着你远行/ 2022年10月24日 13:27/ 0 赞/ 153 阅读

相关给定n个数，求n个数的两两异或和

给定n个数，求n个数的两两异或和 include <bits/stdc++> using namespace std; define ll long

悠悠/ 2022年08月30日 04:10/ 0 赞/ 226 阅读

相关求阶梯状数组的层数和第n行的第一个数和第n个数？

<?php header('content-type:text/html;charset=utf-8;'); $max_num

亦凉/ 2022年05月31日 12:09/ 0 赞/ 207 阅读

相关 JavaScript求n个数的最大值

<!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>Document</

╰+攻爆jí腚メ/ 2022年05月20日 02:57/ 0 赞/ 203 阅读