题解 | #丑数#

第七十二题

维护三个指针，分别表示 最后一次*235的值的位置
原理看答案的图思考一下 我表述不出来QAQ

大致思想就是每次找最后乘235的最后一个，并且乘的东西，是在ans中依次找下去的，用过了，就找ans后一个。

ans中依次存储的都是最小的，再依次比较最小的乘235谁大谁小。

......看答案解析吧 -> _ ->

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        // 丑数的定义为只由235的乘积组成
        
        // i用来维护和更新最新的ans
        // num235从头开始计算，记录乘235的最后一次 所在的位置
        // 每次只要从三个索引的位置 找到*2或3或5 中最小的 并更新num235
        
        // 1 0 0    2
        // 1 1 0    3
        // 2 1 0    4
        // 2 1 1    5
        // 3 2 1    6
        // 下一次找 就是从ans[3]*2,ans[2]*3,ans[1]*5 找最小值
        // ans里面都是最小的了，再往后肯定更大
        // 去看看讲解的演示吧QAQ
        int num2=0,num3=0,num5=0;
        int*ans=new int[index];
        ans[0]=1;
        for(int i=1;i<index;i++)
        {
            ans[i]=min(min(ans[num2]*2,ans[num3]*3),ans[num5]*5);
            if(ans[i] == ans[num2]*2)
                num2++;
            if(ans[i]==ans[num3]*3)
                num3++;
            if(ans[i]==ans[num5]*5)
                num5++;
//             cout<<num2<<num3<<num5<<endl;
        }
    return ans[index-1];
    }
};