梁越

剑指33-丑数

0 人看过

穷举,多解法

这个拿到我只能想到暴力遍历,遍历每个数,看是不是丑数,那怎么判断丑数呢:

一个数只要能被2或3或5整除,就一直除以这三个数,最后结果为1,则为丑数,不为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:

丑数都是又丑数*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];
    }
};