题解 | #丑数#

首先给出暴力法
从1开始判断是否是丑数，若是则count++。
每趟遍历都n++。
当count==index时，返回当前数，即为对应丑数。
这种做法逻辑上是完全没问题的，就是时间复杂度过高。提交运行时会在第11个用例(共13个)处超时，其输入为1500。
这种算法的核心在判断一个数是否是丑数，具体体现为judge函数的实现。每次判断一个数是否能被2，3，5整除，若能，则将该数除以对应的2，3，5后递归调用judge，当输入为1时，返回true，否则返回false。

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        int count = 0;
        int n = 1;
        while(true){
            if(judge(n)){
                count++;
            }
            if(count == index){
                return n;
            }
            n++;
        }
        return -1;
    }
    bool judge(int n){
        if(n == 1){
            return true;
        }
        if(n % 2 == 0){
            return judge(n / 2);
        }
        if(n % 3 == 0){
            return judge(n / 3);
        }
        if(n % 5 == 0){
            return judge(n / 5);
        }
        return false;
    }
};

比起一个数一个数的找，按顺序生成丑数要快得多。
核心思路是按顺序每次生成一个丑数，生成到第index个即为目标数。
观察题目对丑数的定义可以知道，丑数是(2^n1)x(3^n2)x(5^n3)，所以可以根据这个通项公式生成丑数。
难点在于如何确定顺序。解决办法是每次生成三个丑数，选出最小的加入数组，并将用于生成该丑数的幂的次数++。
这种生成方式会重复生成一个数，所以当一个数同时可以整除两个或三个数时，就需要将两个或三个幂的次数++。

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        if(index < 7){
            return index;
        }
        int i2 = 0;
        int i3 = 0;
        int i5 = 0;
        vector<int> res;
        res.push_back(1);
        for(int i = 1;i < index;i++){
            int n1 = res.at(i2) * 2;
            int n2 = res.at(i3) * 3;
            int n3 = res.at(i5) * 5;
            int min = n1 > n2 ? n2 : n1;
            min = min > n3 ? n3 : min;
            res.push_back(min);
            if(res.at(i) == res.at(i2) * 2){
                i2++;
            }
            if(res.at(i) == res.at(i3) * 3){
                i3++;
            }
            if(res.at(i) == res.at(i5) * 5){
                i5++;
            }
        }
        return res.at(index - 1);
    }
};