20 丑数

0 引言

题目：把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 
习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

1 抽象问题具体化

举例：求按从小到大的第8个丑数。

　　解法1：列举法：1，2，3，4，5，6，8，9.

　　解法2：利用原理 丑数必为另一个丑数与2/3/5相乘之积

2 具体问题抽象分析

（1）第一种解法算法描述

　　1. 进入循环，for 1: 不知道啥时候

　　2. 对每一个数进行判断，如果某个数满足丑数的定义，则count ++；

　　3. 直到count == index，停止循环，输出结果.

（2）第二种解法算法描述　　

 　　1. 构建丑数数组，从小到大排列

　　 2. 利用1中的数组，寻找下一个丑数，加入到数组中

　　 3. 直到数组的size达到index为止 

3 demo

bool isUglyNumber(int num){
    while(num %2 == 0)
        num /= 2;
    while(num %3 == 0)
        num /= 3;
    while(num %5 == 0)
        num /= 5;
    return (n == 1)? true : false;
}
int GetUglyNumber_Solution(int index) {
    if(index < 1)
        return 0;
    int count = 0;
    for(int i=1;;i++){
        if(isUglyNumber(i))
            ++ count;
        if(count == index)
            return i;
    }        
} 

该解法的时间复杂度非常高，遍历次数取决于该丑数有多大，在实际应用中算得很慢。

4 代码优化 

int GetUglyNumber_Solution(int index) {
    if(index < 1)
        return 0;
    vector<int> uglyNums;
    uglyNums.push_back(1);
    int t2 =0, t3=0, t5 =0;
for(int i=0;i<index;i++){
        // *2
        int m2 =1, m3=1,m5=1;
        for(int j = t2; j<uglyNums.size(); j++){
            m2 = uglyNums[j] * 2;
            if(m2 > uglyNums[uglyNums.size()-1]){
                t2 = j;
                break;
            }                    
        }
        // *3
        for(int j = t3; j<uglyNums.size(); j++){
            m3 = uglyNums[j] * 3;
            if(m3 > uglyNums[uglyNums.size()-1]){
                t3 = j;
                break;
            }                    
        }
        // *5
        for(int j = t5; j<uglyNums.size(); j++){
            m5 = uglyNums[j] * 5;
            if(m5 > uglyNums[uglyNums.size()-1]){
                t5 = j;
                break;
            }                    
        }
        uglyNums.push_back(min(min(m2,m3),m5));
    }
    return uglyNums[index-1];
}

实际测试，快了不止一星半点。以计算第10000个丑数为例，3中的方法要循环 288325195312500000次，而4中的方法只需要循环5000次即可。