程序员面试题精选100题（37）-寻找丑数[算法] (4)

T₂。对乘以3和5而言，存在着同样的T₃和T₅。

有了这些分析，我们不难写出如下的代码：

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;