第n个丑数

题目描述

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

分析基础：根据丑数的定义，我们可以知道丑数可以由另外一个丑数乘以2，3或者5得到。因此我们可以创建一个数组，里面的数字是排好序的丑数，每一个丑数都是前面的丑数乘以2，3或者5得到的。

 public int GetUglyNumber_Solution(int index) {
        if(index<7)
            return index;
        int i2=0,i3=0,i5=0;
        int [] num=new int[index];
        num[0]=1;
        for(int i=1;i<index;i++){
           num[i]=(Math.min(num[i2]*2,Math.min(num[i3]*3,num[i5]*5)));
            if(num[i]==num[i2]*2) i2++;
            if(num[i]==num[i3]*3) i3++;
            if(num[i]==num[i5]*5) i5++;
        }
        return num[index-1];
    }

第n个丑数

链接：https://www.nowcoder.com/questionTerminal/6aa9e04fc3794f68acf8778237ba065b
来源：牛客网

/*

说下思路，如果p是丑数，那么p=2^x * 3^y * 5^z

那么只要赋予x,y,z不同的值就能得到不同的丑数。

如果要顺序找出丑数，要知道下面几个特（fei）点（hua）。

对于任何丑数p：

（一）那么2*p,3*p,5*p都是丑数，并且2*p<3*p<5*p

（二）如果p<q, 那么2*p<2*q,3*p<3*q,5*p<5*q

现在说说算法思想：

    由于1是最小的丑数，那么从1开始，把2*1，3*1，5*1，进行比较，得出最小的就是1

的下一个丑数，也就是2*1，

    这个时候，多了一个丑数‘2’，也就又多了3个可以比较的丑数，2*2，3*2，5*2，

这个时候就把之前‘1’生成的丑数和‘2’生成的丑数加进来也就是

(3*1,5*1,2*2，3*2，5*2)进行比较，找出最小的。。。。如此循环下去就会发现，

每次选进来一个丑数，该丑数又会生成3个新的丑数进行比较。

    上面的暴力方法也应该能解决，但是如果在面试官用这种方法，估计面试官只会摇头吧

。下面说一个O（n）的算法。

    在上面的特（fei）点（hua）中，既然有p<q, 那么2*p<2*q，那么

“我”在前面比你小的数都没被选上，你后面生成新的丑数一定比“我”大吧，那么你乘2

生成的丑数一定比我乘2的大吧，那么在我选上之后你才有机会选上。

其实每次我们只用比较3个数：用于乘2的最小的数、用于乘3的最小的数，用于乘5的最小的

数。也就是比较(2*x , 3*y, 5*z) ，x>=y>=z的，

重点说说下面代码中p的作用：int p[] = new int[] { 0, 0, 0 }; p[0]表示最小用于

乘2比较数在数组a中的【位置】。 */

题目描述

相关推荐