题目的主要信息：

• 把只包含质因子2、3和5的数称作丑数
• 求按从小到大的顺序的第n个丑数
• 1视作第一个丑数
• 要求：空间复杂度$O(n)O(n)$，时间复杂度$O(n)O(n)$

方法一：最小堆（能过，时间不符合要求）

具体做法：

我们都知道如果$xx$是丑数，则$2x2x$、$3x3x$、$5x5x$都是丑数，丑数也是从1开始由每个丑数这样构建而来的，我们要做的就是找到前$nn$个，即最小的$nn$个。

我们可以利用小顶堆，每次取出堆顶元素一定是最小的，一共取$nn$次就可以了，每次取出来的元素我们分别乘2、乘3、乘5后入堆，当然为了防止重复比如$2\ast 3=62*3=6$、$3\ast 2=63*2=6$，我们还要用无序哈希表去重。

这里面有的数字会超过int的表示范围，因此哈希表和小顶堆都用long。

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        if(index == 0)
            return 0; //排除0
        vector<int> factors = {2, 3, 5}; //要乘的因数
        unordered_map<long, int> mp; //去重
        priority_queue<long, vector<long>, greater<long>> pq; //小顶堆
        mp[1LL] = 1; //1先进去
        pq.push(1LL);
        int res = 0;
        for(int i = 0; i < index; i++){ 
            long cur = pq.top(); //每次取最小的
            pq.pop();
            res = (int)cur;
            for(int j = 0; j < 3; j++){
                long next = res * factors[j]; //乘上因数
                if(mp.find(next) == mp.end()){  //只取未出现过的
                    mp[next] = 1;
                    pq.push(next);
                }
            }
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：$O(nlo{g}_{2}n)O(nlog\_2n)$，一共循环$nn$次，取$nn$次最小值，每次循环中最多有3次 入堆操作，每次入堆都是$O(lo{g}_{2}n)O(log\_2n)$，无序哈希表的操作是$O(1)O(1)$
• 空间复杂度：$O(n)O(n)$，无序哈希表和小顶堆最大空间为$3\ast n3*n$的长度

方法二：动态规划

具体做法：

我们知道丑数是由1开始的每个丑数依次乘上2、3、5得到，而我们每次只需要在其中找到最小的一个，一共找$nn$次即可。我们可以用$ii$、$jj$、$kk$三个下标表示在已经找到的丑数中那个数分别被乘2、乘3、乘5有无被记录过。

class Solution {
public:
    int findMin(int x, int y, int z){  //寻找三个数中的最小值
        int res = x; 
        res = y < res ? y : res;
        res = z < res ? z : res;
        return res;
    }
    int GetUglyNumber_Solution(int index) {
        if(index == 0)
            return 0; //排除0
        vector<int> num; //按顺序记录丑数
        num.push_back(1);
        int count = 1; //记录这是第几个丑数
        int i = 0, j = 0, k = 0; //分别代表要乘上2 3 5的下标
        while(count < index){
            num.push_back(findMin(num[i] * 2, num[j] * 3, num[k] * 5)); //找到三个数中最小的丑数
            count++;
            if(num[count - 1] == num[i] * 2)
                i++; //由2与已知丑数相乘得到的丑数，那该下标及之前的在2这里都用不上了
            if(num[count - 1] == num[j] * 3)
                j++; //由3与已知丑数相乘得到的丑数，那该下标及之前的在3这里都用不上了
            if(num[count - 1] == num[k] * 5)
                k++; //由5与已知丑数相乘得到的丑数，那该下标及之前的在5这里都用不上了
        }
        return num[count - 1];
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，只需要遍历一次
• 空间复杂度：$O(n)O(n)$，记录丑数的数组最大长度为$nn$