剑指33-丑数

一个数只要能被2或3或5整除，就一直除以这三个数，最后结果为1，则为丑数，不为1，则不为丑数

class Solution { //效率太低不通过
public:
    int GetUglyNumber_Solution(int index) {
        int res = 0;
        int i = 0;
        while (index)
        {
            if (isUglyNumber(i)) {
                index--;
                res = i;
            }
            i++;
        }
        return res;
    }

    bool isUglyNumber(int num)
    {
        if (num <= 0) return false;
        while (num % 2 == 0) num /= 2;
        while (num % 3 == 0) num /= 3;
        while (num % 5 == 0) num /= 5;
        return (num == 1) ? true : false;
    }
};

丑数都是又丑数*2或*3或*5得来的，只要我们用丑数一直乘这三个数，并更新底数，就能得到所有的丑数，但是这样得到的丑数无序而且还有重复的
可以用一个数组来存储下一个应该存放的值，定义三个指针p2, p3, p5，记录的是当前的位置，初始化为0
然后每次p2的值*2，p3的值*3，p5的值*5，选取这三个中最小的那个放在数组后面
添加后，对应指针向前++
这样可以保证每次添加的丑数都在正确位置

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        if (index <= 0) return 0;
        vector<int> res(index, 0);
        res[0] = 1;
        int p2 = 0, p3 = 0, p5 = 0;
        for (int i = 1; i < index; i++)
        {
            res[i] = min(res[p2] * 2, min(res[p3] * 3, res[p5] * 5)); //关键点，选取最小的
            if (res[i] == res[p2] * 2) p2++;
            if (res[i] == res[p3] * 3) p3++;
            if (res[i] == res[p5] * 5) p5++;
        }

        return res[index - 1];
    }
};