题解 | #丑数#

由题意可知，丑数的定义为：(2^x)*(3^y)*(5^z);

首先可以想到第一种方法，即从2开始判断每个数是不是丑数，直到发现了第idx个丑数，此即为暴力解。

代码不多赘述。

此外，可以想到，我们已经知道了丑数的定义，那么我们可以直接自己生成丑数，然后选择第idx个最小的丑数即可。

又因为通过不同基数生成的丑数可能会有重复，所以我们可以利用set的自动去重功能，所以使用set来存放生成的丑数

另外使用一个额外的容器来存放每次取得的最小的丑数，即相当于对前idx个丑数进行排序

代码如下：

typedef long long ll;
class Solution {
  public:
    int GetUglyNumber_Solution(int idx) {
        if(idx==0){
            return 0;
        }
        set<ll> st;
        vector<ll> res;
        res.push_back(1);
        ll p = 0;
        while(res.size()<idx){
            st.insert(res[p]*2);
            st.insert(res[p]*3);
            st.insert(res[p]*5);
            res.push_back(*st.begin());
            st.erase(st.begin());
            p++;
        }
        return res[idx-1];
    }
};