丑数问题

问题描述：

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

问题分析：

     第一个丑数为1，后面求丑数可根据思想，若p为丑数，则2*p,3*p,5*p均为丑数，换句话说，丑数可以通过已是丑数的数乘以2或3或5形成，但考虑到从小到大的问题。所以可以通过三个变量i2,i3,i5控制乘2、乘3和乘5的操作进行。

代码如下：

publicclassSolution {

publicintGetUglyNumber_Solution(intindex)

{

if(index<=0)

return0;

intresult[] =newint[index];

result[0] =1;

inti =1;

inti2=0,i3=0,i5=0;

while(i

{

inttemp = min(result[i2]*2,min(result[i3]*3,result[i5]*5));//每次只需比较*2和*3和*5中最小的

if(temp ==result[i2]*2) i2++;//这三句起到了遍历和去重的效果；

if(temp ==result[i3]*3) i3++;//比如2*3和3*2为同一个数，result[1] = 2,result[2]=3故此处操作

if(temp ==result[i5]*5) i5++;//可将result[1]*3和result[2]*2去掉重复。

result[i++] = temp;

}

returnresult[index-1];

}

publicstaticintmin(inta,intb)

{

ints = (a < b?a:b);

returns;

}

}

--daytwo