一、题目
二、思路
方法一：小顶堆
求前k大经常用到优先级队列，小顶堆，循环将符合要求的丑数加入小顶堆，取k次堆顶元素即可让堆顶为第k个丑数。而逐个加入丑数即加入2 x 2x2x、3 x 3x3x、5 x 5x5x进入集合（去重）即可。注意这里加入小顶堆的元素不能是int类型，否则会报错overflow（因为next = temp * factor后可能会越界）：
Line 17: Char 33: runtime error: signed integer overflow: 429981696 * 5 cannot be represented in type 'int' (solution.cpp)
三、方法一：小顶堆
class Solution { public: int nthUglyNumber(int n) { vector<int> fac = {2, 3, 5}; //用int还不够 unordered_set<long>s; //注意小顶堆用greater priority_queue<long, vector<long>, greater<long>>min_heap; s.insert(1L); min_heap.push(1L); int ugly = 0; for(int i = 0; i < n; i++){ long temp = min_heap.top(); min_heap.pop(); ugly = (int)temp; for(int factor: fac){ long next = temp * factor; if(!s.count(next)){ s.insert(next); min_heap.push(next); } } } return ugly; } };
四、方法二：动态规划
方法二：动态规划
小顶堆会预存较多丑数，维护小顶堆的时间和空间复杂度较高。
简单说就是把所有丑数列出来，然后从小到大排序。而大的丑数必然是小丑数的2/3/5倍，所以有下面这3个数组。每次就从那数组中取出一个最小的丑数归并到目标数组中。
nums2 = {1*2, 2*2, 3*2, 4*2, 5*2, 6*2, 8*2...} nums3 = {1*3, 2*3, 3*3, 4*3, 5*3, 6*3, 8*3...} nums5 = {1*5, 2*5, 3*5, 4*5, 5*5, 6*5, 8*5...} // 注意 7 不是丑数. // 2, 3, 5 这前 3 个丑数一定要乘以其它的丑数， 所得的结果才是新的丑数， 所以上例中没有出现 7*2, 7*3, 7*5
现在问题其实转化为合并3个上面这样的有序序列，常规方法即每个序列各维护一个指针，然后每次将最小的元素加入数组中，并且此时要将对应指针后移一个元素，具体根据动态规划的四部曲分析：
（1）确定状态
定义数组 d p [ i ] dp[i]dp[i]，其中 d p [ i ] dp[i]dp[i] 表示第 i 个丑数，第 n 个丑数即为 d p [ n ] dp[n]dp[n]。
（2）状态转移方程：n大于等于2时：
（3）边界+初始条件：最小的丑数是1，dp[1]=1。
（4）计算顺序：从小到大遍历。
class Solution { public: int nthUglyNumber(int n) { vector<int>dp(n + 1, 0); dp[1] = 1; int p2 = 1, p3 = 1, p5 = 1; for(int i = 2; i <= n; i++){ int num2 = dp[p2] * 2, num3 = dp[p3] * 3, num5 = dp[p5] * 5; dp[i] = min(min(num2, num3), num5); if(dp[i] == num2){ p2++; } if(dp[i] == num3){ p3++; } if(dp[i] == num5){ p5++; } } return dp[n]; } };
