题解 | #丑数#

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        int factors[] = {2, 3, 5};
        unordered_set<long> hash; // 哈希表防止有重复数进入
        priority_queue<long,vector<long>, greater<long>> heap; // 小顶堆输出第n个丑叔
        hash.insert(1);
        heap.push(1);
        int ugly = 0;
        for(int i = 0; i < index; i++) {
            int cur = heap.top();
            heap.pop();
            ugly = (int)cur;
            for(auto factor:factors) {
                long x = cur * factor;
                if(!hash.count(x)){
                    hash.insert(x);
                    heap.push(x);
                }
            }
        }
        return ugly;
    }
};