下次谷歌的技术总监面试题研究了很久还是疑惑，关于丑数，求大牛给点标准的分析

上次谷歌的技术总监面试题研究了很久还是疑惑，关于丑数，求大牛给点标准的分析
9.Ugly numbers are numbers whose only prime factors are 2,3or 5.The sequence 1,2,3,4,5,6,8,9,10,12,15,…shows the first 11ugly numbers. By convention,1 is included.Write a time efficient program to find and print the 1500’th ugly number.(20 points)

从网络上找了个答案
感觉很难理解，尤其是 ++nextUglyIndex;会不会引起越界呢，有没有条件的朋友帮忙跑下程序

int GetUglyNumber_Solution2(int index)

{

    if(index <= 0)

        return 0;

 

    int *pUglyNumbers = new int[index];

    pUglyNumbers[0] = 1;

    int nextUglyIndex = 1;

 

    int *pMultiply2 = pUglyNumbers;

    int *pMultiply3 = pUglyNumbers;

    int *pMultiply5 = pUglyNumbers;

 

    while(nextUglyIndex < index)

    {

        int min = Min(*pMultiply2 * 2, *pMultiply3 * 3, *pMultiply5 * 5);

        pUglyNumbers[nextUglyIndex] = min;

 

        while(*pMultiply2 * 2 <= pUglyNumbers[nextUglyIndex])

            ++pMultiply2;

        while(*pMultiply3 * 3 <= pUglyNumbers[nextUglyIndex])

            ++pMultiply3;

        while(*pMultiply5 * 5 <= pUglyNumbers[nextUglyIndex])

            ++pMultiply5;

 

        ++nextUglyIndex;

    }

 

    int ugly = pUglyNumbers[nextUglyIndex - 1];

    delete[] pUglyNumbers;

    return ugly;

}

 

int Min(int number1, int number2, int number3)

{

    int min = (number1 < number2) ? number1 : number2;

    min = (min < number3) ? min : number3;

 

    return min;

}

[解决办法]
++nextUglyIndex 不会引起越界的吧， 最大也才是 nextUglyIndex == index

int ugly = pUglyNumbers[nextUglyIndex - 1]; 

引用的时候是 减了一的
[解决办法]
主函数呢？。。
[解决办法]
主函数这样写就可以了：

#include <stdio.h>
#include <stdlib.h>

int main()
{
GetUglyNumber_Solution2(1500); 
 
system("pause");

return 0;
}

最后结果是859963392
[解决办法]
我写了个超低速程序验证，结果

bool IsDivisibleBy2_3_5(int num)
{
int remainder = 0;
while(true)
{
remainder = num % 2;
if(remainder != 0)
{
break;
}
num /= 2;
}

while(true)
{
remainder = num % 3;
if(remainder != 0)
{
break;
}
num /= 3;
}

while(true)
{
remainder = num % 5;
if(remainder != 0)
{
break;
}
num /= 5;
}
/*if(num == 1)
cout<<"yes"<<endl;
else
cout<<"no"<<endl;*/
return num == 1;
}


int GetUglyNumber_Solution2(int index)

{
    if(index <= 0)
        return 0;

int ugly, test;

    ugly = test = 1;
for(int i=0; i<index; )
{
while(true)
{
if( IsDivisibleBy2_3_5(test) )
{
i++;
ugly = test;
cout<<test<<" "<<endl;
test++;

break;
}
else
test++;
}
}
    return ugly;
}


int main()
{
GetUglyNumber_Solution2(1500);

system("pause");
return 0;
}
 

 

查看更多 下一篇