一、题目

二、思路

求前k大经常用到优先级队列，小顶堆，循环将符合要求的丑数加入小顶堆，取k次堆顶元素即可让堆顶为第k个丑数。而逐个加入丑数即加入$2x$、$3x$、$5x$进入集合（去重）即可。注意这里加入小顶堆的元素不能是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;//小顶堆用greaterpriority_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;}
};