题解 | #丑数#

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        int a = 2, b = 3, c = 5;
        int a_n = 0, b_n = 0, c_n = 0;//统计第n个丑数包含对应的a、b、c个数
        vector<int> v_un(1, 1);
        while (v_un.size() < index) {
            a = v_un[a_n]*2;// 注意当前的丑数，可由之前的之前的数乘以基础因子得到
            b = v_un[b_n]*3;// 至于是之前哪个丑数，可通过x_n记录
            c = v_un[c_n]*5;
            int val = min(a, min(b, c));
            v_un.push_back(val);
            if(val == a) a_n++;// 记录当前丑数，含基础因子次数
            if(val == b) b_n++;
            if(val == c) c_n++;
        }
        return v_un[index-1];
    }
    // bool judge(int num)
    // {
    //     while (!num%2) num/=2;
    //     while (!num%3) num/=3;
    //     while (!num%5) num/=5;
    //     if(num == 1) return true;
    //     else return false; 
    // }

    // int GetUglyNumber_Solution(int index) {
    //     // write code here
    //     int val = 1;
    //     int count = 1;
    //     while (true) {
    //         if(count == index)
    //         {
    //             return val;
    //         }
    //         if(judge(val))
    //         {
    //             std::cout << val << " " << count << std::endl;
    //             count++;
    //         }
    //         val++;
    //     }
    //     return val;
    // }
};