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

2后大于M的结果，记为M₂。同样我们把已有的每一个丑数乘以3和5，能得到第一个大于M的结果M₃和M₅。那么下一个丑数应该是M₂、M₃和M₅三个数的最小者。

前面我们分析的时候，提到把已有的每个丑数分别都乘以2、3和5，事实上是不需要的，因为已有的丑数是按顺序存在数组中的。对乘以2而言，肯定存在某一个丑数T₂，排在它之前的每一个丑数乘以2得到的结果都会小于已有最大的丑数，在它之后的每一个丑数乘以2得到的结果都会太大。我们只需要记下这个丑数的位置，同时每次生成新的丑数的时候，去更新这个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;

    }

 

    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;

}

和第一种思路相比，这种算法不需要在非丑数的整数上做任何计算，因此时间复杂度要低很多。感兴趣的读者可以分别统计两个函数GetUglyNumber_Solution1(1500)和GetUglyNumber_Solution2(1500)