面试题34:丑数

题目:我们把只包含因子2,3和5的数称作丑数。求按从小到大的顺序的第1500个丑数。例如6,8都是丑数,但14不是,因为它包含因子7.习惯上我们把1当做第一个丑数。


分析

最直观的方法是从1往后逐个判断每个数字,并设一个计数器。如果一个数是丑数,计数器加一。当计数器到1500时,输出这个数即可。但求一个数的所有因子的时间复杂度为O(n0.5)(对否?),总的时间复杂度为O(n1.5)。

更好的一种方法是以空间换时间,即创建一个数组保存已经找到的丑数,这样就不用重复计算前面已经计算过的。而是每次用数组中的一个数来计算出下一个丑数。一般我们会选择数组中2,3,5对应的最后一个数来计算下一个丑数,所以需要使数组是有序的。因此可以用3个变量T2,T3,T5来指示2,3,5对应的最后一个丑数,然后用着三个数分别乘以2,3和5得到R2,R3和R5。只需要将R2,R3,R5中的最小者放入数组中即可,并更新相应的T2,T3或T5。

代码如下:

{
    int min=a>b?b:a;
    min=min>c?c:min;
    return min;
}

int GetUglyNumber(int index)
{
    if(index<=0)
        return 0;
    vector<int> v;
    v.push_back(1);
    int M2=0,M3=0,M5=0;
    while(v.size()<index)
    {
        int min=Min(v[M2]*2,v[M3]*3,v[M5]*5);
        v.push_back(min);
        while(v[M2]*2<=v[v.size()-1])
            M2++;
        while(v[M3]*3<=v[v.size()-1])
            M3++;
        while(v[M5]*5<=v[v.size()-1])
            M5++;
    }
    return v[v.size()-1];
}

以上

如果你有任何想法或是可以改进的地方,欢迎和我交流!

完整代码及测试用例在github上:点我前往

[来自为知笔记(Wiz)](http://www.wiz.cn/i/96171253 "来自为知笔记(Wiz)")