题目描述

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

方法1(最笨的方法)

思路

依次判断每一个整数是否为丑数，但是这种方法的时间效率太低，因为需要对每一个整数进行判断(但是这种方法我也没想到)
丑数满足：(1)包含2,3,5的因子 (2)只包含2,3,5的因子
(1) 如果能整除2/3/5——number%2==0就代表含有2/3/5的因子
(2) 只含有，如果能整除2，那就除以2；如果能整除3，那就除以3；如果能整除5，那就除以5；直到最后如果为1，则表示是丑数，如果不是，则不是丑数

代码

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        if(index==1)
            return 1;
        int count=1;  //第一个丑数为1
        for(int i=2;;i++)
        {
            int number=i;
            while(number%2==0)
                number/=2;
            while(number%3==0)
                number/=3;
            while(number%5==0)
                number/=5;
            if(number==1)
                count++;
            if(count==index)
                return i;
        }
    }
};

方法2(创建一个数组)

思路

列些一些丑数可以发现一个规律，每个丑数都等于前面的丑数乘以2或3或5，所以我们可以创建一个数组，里面的数字是排好序的丑数，之后就可以对数组里的每个丑数乘以2,3,5，取最小值跟在这个数组后面；但是如果每一次都把数组里的所有值乘以2,3,5就会有很多已经在数组里的发生重复，我们可以对于2,3,5分别定义一个类似指针t2,t3,t5；如果数组里的某个数已经乘了2，那t2就往后一个(往后肯定是更大的，因为这是个排好序的数组)
代码如下，有两个注意点：
(1) 数组下标从0开始，但是丑数数数是从1开始的
(2) min函数只能比较两个数

代码

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        if(index<7)
            return index;  //穷举法找到规律，1~6个丑数就是1~6
        vector<int> res(index);//初始化一个数组，数组长度为index个(注意下标是从0开始的)
        res[0]=1;
        int t2=0,t3=0,t5=0;
        for(int i=1;i<index;i++)
        {
            res[i]=min(res[t2]*2,min(res[t3]*3,res[t5]*5)); //min函数只能比较两个数
            if(res[i]==res[t2]*2)
                t2++;
            if(res[i]==res[t3]*3)
                t3++;
            if(res[i]==res[t5]*5)
                t5++;
        }
        return res[index-1];  //这里一定要注意

    }
};