[剑指 Offer] 49. 丑数

[frdmu]

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

 

示例:

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

说明:  

• 1 是丑数。
• n 不超过1690。

 

解法：
代码如下：

class Solution {
public:
    int nthUglyNumber(int n) {
        priority_queue<long, vector<long>, greater<long>> heap;
        unordered_set<long> hash;
        vector<int> factors{2, 3, 5};

        heap.push(1);
        hash.insert(1);
        int res, cnt = 0;
        while (!heap.empty()) {
            res = heap.top();
            cnt++;
            if (cnt == n) break;
            heap.pop();
            for (auto factor: factors) {
                long tmp = (long)res * factor;
                if (hash.count(tmp) == 0) {
                    heap.push(tmp);
                    hash.insert(tmp);
                }
            }
        }

        return res;
    }
};

类似题目：
[LeetCode] 264. Ugly Number II