题目描述

分析:1,2,3,4,5,6都是丑数,所以,当n<7时候,丑数的个数位 .

丑数的形式就是2^x 3^y 5^z

图片参考B站上的解析:https://www.bilibili.com/video/BV1CK411c7gx?p=43

这个讲解采用作图方式,是比较清晰直观的.

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        //由规律可知,当1<=index<=7时,1,2,3,4,5,6,7都是丑数
        //因此
        if(index<7) return index;
        vector<int> v;//存放丑数数组
        //定义三个指针p2,p3,p5,分别表示质因子位2,3,5的数字
        int p2 ,p3 ,p5;
         p2 = p3 = p5 =0;//都指向数组v下标位0的位置
        v.push_back(1);//数组第一个位置存放元素1,故已经找到了第一个
        //循环体中,丑数从第二个开始寻找
        for(int i =2 ;i<=index;i++){
            //把最小值放到数组v中
            int minValue = min(v[p2]*2,v[p3]*3);
            minValue = min(minValue,v[p5]*5);
            //将最小值放入数组中
            v.push_back(minValue);
            //寻找那些是最小值,是最小值的,指针向后移动
            if(minValue == v[p2]*2) p2+=1;
            if(minValue == v[p3]*3) p3+=1;
            if(minValue == v[p5]*5) p5+=1;
        }
        return v[v.size()-1];
    }
};