题解 | 丑数

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param index int整型 
     * @return int整型
     */
    int GetUglyNumber_Solution(int index) {
        // write code here
        if(index<=0)return 0;//简单错误处理
        vector<long long> uglyNums;
        uglyNums.push_back(1);
        int t2 = 0, t3 = 0, t5 = 0;
        int cnt = 1;
        while(cnt<index){
            ++cnt;
            long long curMax = uglyNums.back();
            long long nextMax = min(min(uglyNums[t2]*2, uglyNums[t3]*3), uglyNums[t5]*5);
            uglyNums.push_back(nextMax);
            while(uglyNums[t2]*2<=nextMax) ++t2;
            while(uglyNums[t3]*3<=nextMax) ++t3;
            while(uglyNums[t5]*5<=nextMax) ++t5;
        }
        return uglyNums.back();
    }
};

只要确保不是大数问题，数字又很大就开long long吧。

确定我们下一次选择的值会比当前最大丑数大，所以所有的选择都要往后走到合适位置（显然在最后一个之前，所以无需验证越界）

然后从比当前最大丑数大的三个可能性中选，选好后更新3个选择点。

主要是解决了重复问题。