丑数

思路

1、使用一个数组保存之前的丑数
2、更新下一个丑数的时候只需要比较三个值即可
3、所以，程序的核心就是维护好三个值（对应的下标）

代码

class Solution {
public:
    bool isUgly(int x ){

        while(x%2==0){
            x = x/2;
        }

        while(x%3==0){
            x=x/3;
        }

        while(x%5==0){
            x=x/5;
        }

        return 1==x;

    }
    /*
    int GetUglyNumber_Solution(int index) {
        if(index==1){
            return 1;
        }
        // 最笨的方法
        int count=1;
        int i = 2;
        while(1){
            if(isUgly(i)){
                count++;

            }
            if(count==index){
                return i;
            }
            i++;
        }
        return 0;

    }
    */
    int GetUglyNumber_Solution(int index){

        // 初始化
        if(index < 5){
            vector<int> ugly_arr ={ 1, 2, 3, 4, 5};
            return ugly_arr[index-1];
        }
        vector<int> ugly_arr(index, 0);
        ugly_arr[0] = 1;
        ugly_arr[1] = 2;
        ugly_arr[2] = 3;
        ugly_arr[3] = 4;
        ugly_arr[4] = 5;

        // 初始化要维护的三个index
        int t2_index = 2;
        int t3_index = 1;
        int t5_index = 1;

        int cur_lne = 5;

        while(cur_lne < index){
            // 获取三个候选值
            int M2 = ugly_arr[t2_index]*2;
            int M3 = ugly_arr[t3_index]*3;
            int M5 = ugly_arr[t5_index]*5;

            // 取三个候选值的最小值作为下一个丑数
            vector<int> tmp = {M2, M3, M5};
            auto min_ugly = *(min_element(tmp.begin(), tmp.end()));
            ugly_arr[cur_lne] = min_ugly;
            cur_lne++;

            // 维护更新三个下标
            if(M2 == min_ugly){
                t2_index++;
            }
            if(M3 == min_ugly){
                t3_index++;
            }

            if(M5 == min_ugly){
                t5_index++;
            }

        }

        return ugly_arr[--index];



    }
};