学步园

我们把只包含因子2、3和5的数称为丑数（Ugly Number）。求从小到大的顺序的第1500个丑数。习惯上我们把1当做第一个丑数。

这道题暴力的解法就是按照顺序检查每一个数是不是丑数。

判断一个数是不是丑数的函数如下：

bool IsUglyNumber(int num)

{

       while(num%2==0)

              num/=2;

       while(num%3==0)

              num/=3;

       while(num%5==0)

              num/=5;

       returnnum==1?true:false;

}

从1开始，按顺序检查，如果这个数是丑数，加1，直到1500个丑数为止。

int GetUglyNumber1(int index)

{

       if(index<1)

              return0;

       intnumber=0;

       intcount=0;

       while(count<index)

       {

              number++;

              if(IsUglyNumber(number))

                     ++count;

       }

       returnnumber;

}

这个代码非常整洁，但最大的问题每一个整数都需要计算。即使这个数字不是丑数，我们还是需要对它进行求余和除法操作。该算法的效率是很低的。

我们应该试着找到一种只需要计算丑数的方法，而不需要在非丑数的整数上面花费时间。根据丑数的定义，丑数应该是另一个丑数乘以2、3、5的结果（1除外）。因此我们可以创建一个数组，里面的数字是排好序的丑数，每一个丑数都是前面的丑数乘以2、3或者5得到。

int min(int a,int b,int c)

{

       intmin=a<b?a:b;

       returnmin<c?min:c;

}

int GetUglyNumber2(int index)

{

       if(index<1)

              return0;

       int*pUglyNumbers=new int[index];

       pUglyNumbers[0]=1;

       intnextIndex=1;

       int*pUgly2=pUglyNumbers;

       int*pUgly3=pUglyNumbers;

       int*pUgly5=pUglyNumbers;

       while(nextIndex<index)

       {

              pUglyNumbers[nextIndex]=min(*pUgly2*2,*pUgly3*3,*pUgly5*5);

              while(*pUgly2*2<=pUglyNumbers[nextIndex])

                     ++pUgly2;

              while(*pUgly3*3<=pUglyNumbers[nextIndex])

                     ++pUgly3;

              while(*pUgly5*5<=pUglyNumbers[nextIndex])

                     ++pUgly5;

              ++nextIndex;

       }

       intugly=pUglyNumbers[nextIndex-1];

       delete[]pUglyNumbers;                //将数组内存释放掉

       returnugly;

}

这种方法需要一定的内存空间，是一种以空间换时间的思想。