4. 丑数 II

作者: 和蔼的zhxing | 来源:发表于2017-12-04 14:19 被阅读141次

    设计一个算法,找出只含素因子2,3,5 的第 n 小的数。
    符合条件的数如:1, 2, 3, 4, 5, 6, 8, 9, 10, 12...
    样例
    如果n = 9, 返回10

    暴力遍历

    暴力遍历,判断一个数是否只有2,3,5的素因子,如果是,放入容器,计数加1,直到找到第n个然后输出就行了,写起来也简单:

    bool IsUgly(int n)
        {
            while(n%2==0)   //可以被2整除的话就除以2,下同
            {
                n/=2;
            }
             while(n%3==0)  
            {
                n/=3;
            }
             while(n%5==0)   
            {
                n/=5;
            }
            if(n==1)   //如果最后除完得到的是1,说明确实只含有2,3,5的因子,则是丑数
            return true;
            else 
            return false;
        }
        int nthUglyNumber(int n)
        {
            int num=1;   //从1开始遍历 
            int index=0;  //记录已找到丑数的个数
            while(1)
            {
                if(IsUgly(num))  index++;  //如果是丑数,那么计数器加1
                if(index==n)  return num;   //如果是第n个,那么就返回
                num++;                      
            }
        }
    

    不出意料大数据的时候时间会超出限制。

    找规律

    这种题说起来都是数学题,只要能找出规律来就能减少运算量。
    注意到这样一个现象:一个丑数乘以2,3,5的话肯定还是丑数,也就是说丑数可以由丑数生成,我们如果只有一个初始值1,那么还是可以生成丑数。我们把丑数序列记作res.
    第二个丑数应该是: min(res[1]*2,res[1]*3,res[1]*5); min(2,3,5)=2
    第三个丑数应该是: min(res[2]*2,res[1]*3,res[1]*5); min(4,3,5)=3
    第三个丑数应该是: min(res[2]*2,res[2]*3,res[1]*5); min(4,6,5)=4

    每次更新只更新一个数十为了保证这样更新的数一定是有序的,我们用了三个指针在这里,2,3,5这三个因子保持不动,哪一个因子作用的数被采纳,我们就把对应的指针+1,移到下一个数上,这样虽然会有重复计算(因为一般情况下我们每次都只更新一个指针),但是可以保证每次更新的都是最小的丑数。如果一个循环中算出了两个最小值,那么对应的两个指针都++,下面是当n等于9的时候的打印日志:

    打印日志
    对应的代码需要注意的是:判断哪个指针指向最小值的if之间不要用else!
    int nthUglyNumber(int n) {
            int start=1;
         
            vector<int> res;      //存放结果
            res.push_back(start);   //第一个数先放进去
            if(n==1)    //处理特殊情况
            return 1;
            int index=1;   //序列号
            int p2,p3,p5;   //记录的是当前乘以2,3,5的数的索引。
            p2=p3=p5=0;   //所以初始化为1,每次枚举三个数
            while(index<n)
            {
                res.push_back(min3(2*res[p2],3*res[p3],5*res[p5]));   //每次把最小的放入数组
                cout<<2*res[p2]<<" "<<3*res[p3]<<" "<<5*res[p5]<<endl;
                if(2*res[p2]==*(res.end()-1))   p2++;   
                //如果刚放入的是2*res[p2],就把p2++,下次就用下一个数乘以2了。
                if(3*res[p3]==*(res.end()-1))   p3++; 
                if(5*res[p5]==*(res.end()-1))   p5++; 
                //上面三个if之间不要用else,因为可能存在多个最小值,都需加1。
                index++;            //索引加1,
            }
            return *(res.end()-1);   //返回最后一个数
            // write your code here
        }
    

    利用set暴力去重排序。

    这样也是可以的,不过计算量也是挺大的,因为还是有大量的重复计算。我就不写了。

    相关文章

      网友评论

        本文标题:4. 丑数 II

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