美文网首页
4. 丑数 II

4. 丑数 II

作者: YOLO_2a2d | 来源:发表于2020-09-16 10:27 被阅读0次

设计一个算法,找出只含素因子2,3,5 的第 n 小的数。

符合条件的数如:1, 2, 3, 4, 5, 6, 8, 9, 10, 12...
样例

样例 1:

输入:9
输出:10

样例 2:

输入:1
输出:1

挑战

要求时间复杂度为 O(nlogn) 或者 O(n)。
注意事项

我们可以认为 1 也是一个丑数


class Solution {
public:
    /**
     * @param n: An integer
     * @return: return a  integer as description.
     */
    int nthUglyNumber(int n) {
        // write your code here
        
        int* res=new int[n];
        
        res[0]=1;
        
        int two=0;
        int three=0;
        int five=0;
        
        for(int i=1;i<n;i++){
            
           // res[i]=Math.min(res[two]*2,res[three]*3,res[five]*5);
            
            if(res[two]*2<res[three]*3){
                res[i]=res[two]*2;
            }else{
                res[i]=res[three]*3;
            }
            
            if(res[i]>res[five]*5){
                res[i]=res[five]*5;
            }
            
            
            if(res[i]==res[two]*2)
                two++;
            
            if(res[i]==res[three]*3)
                three++;
                
            if(res[i]==res[five]*5)
                five++;
            
        }
        
        return res[n-1];
        
    }
};

算法设计思想:

  • 创建三个动态下标充当动态指针,并初始指向初始位;
  • 当对应的下标的值是最小的时候,对应的下标往前一步;

参考链接:https://www.bilibili.com/video/BV1gz411v7C5?t=371

相关文章

  • 4. 丑数 II

    设计一个算法,找出只含素因子2,3,5 的第 n 小的数。符合条件的数如:1, 2, 3, 4, 5, 6, 8,...

  • 4. 丑数 II

    设计一个算法,找出只含素因子2,3,5 的第 n 小的数。 符合条件的数如:1, 2, 3, 4, 5, 6, 8...

  • LintCode 4. 丑数 II

    原题 解 第一步,万年不变的查错。如果给的n是小于1,那么这个就没什么意义了,return 0。 这道题,找只含有...

  • LintCode 4. 丑数 II

    题目描述 设计一个算法,找出只含素因子2,3,5的第n小的数。 符合条件的数如:1, 2, 3, 4, 5, 6,...

  • 丑数II

    题目描述 设计一个算法,找出只含素因子2,3,5 的第 n 大的数。1也是一个丑数。 思路 方法一每个丑数都是2....

  • 丑数 II

    设计一个算法,找出只含素因子2,3,5 的第 n 小的数。 符合条件的数如:1, 2, 3, 4, 5, 6, 8...

  • 丑数 II

    编写一个程序,找出第 n 个丑数。 丑数就是只包含质因数 2, 3, 5 的正整数。 示例: 输入: n = 10...

  • 264-ugly-number-ii

    题目 ugly-number-ii 编写一个程序,找出第 n 个丑数。丑数就是只包含质因数 2, 3, 5 的正整...

  • 4. 丑数(lintcode)

    因为丑数只含素因子2,3,5。所以 任一丑数 = 2或3或5 * 更小的丑数(因为丑数素因子只由2 3 5组成,所...

  • 丑数II ugly-number-ii

    设计一个算法,找出只含素因子2,3,5 的第 n 小的数。 符合条件的数如:1, 2, 3, 4, 5, 6, 8...

网友评论

      本文标题:4. 丑数 II

      本文链接:https://www.haomeiwen.com/subject/ghkmektx.html