算法进阶——丑数

题目

---

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第 n个丑数。

数据范围：0≤n≤2000

要求：空间复杂度 O(n) ， 时间复杂度 O(n)

示例1

输入：
7
返回值：
8

思路

---

利用小顶堆，即优先队列，每次取出堆顶元素一定是最小的，一共取n次就可以了，每次取出来的元素我们分别乘2、乘3、乘5后入堆，即作为之后要访问的数字，当然为了防止重复比如2∗3=6、3∗2=6，我们还要用哈希表去重。

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

解答代码

---

#include <queue>
#include <vector>
class Solution {
public:
    /**
     * @param index int整型 
     * @return int整型
     */
    int GetUglyNumber_Solution(int index) {
        // write code here
        if (index <= 0) {
            return 0;
        }

        // 乘数因子
        vector<int> factors {2, 3, 5};
        // 优先队列(小顶堆)用以获取当前最小的丑数
        priority_queue<long, vector<long>, greater<long>> min_on_top_queue;
        // 记录丑数，从小到大排序，用set也可以去重
        set<long> ugly_numbers;

        min_on_top_queue.push(1);
        ugly_numbers.insert(1);

        long min_ugly_number = 1;
        for (int i = 1; ; i++) {
            // 每次取出当前最小的丑数
            min_ugly_number = min_on_top_queue.top();
            min_on_top_queue.pop();

            if (i == index) {
                break;
            }

            // 分别乘以2,3,5
            for (int i = 0; i < 3; i++) {
                auto new_number = min_ugly_number * factors[i];
                // 在set中不存在，则说明是找到的一个新的丑数
                if (ugly_numbers.find(new_number) == ugly_numbers.end()) {
                    min_on_top_queue.push(new_number);
                    ugly_numbers.insert(new_number);
                }
            }
        }

        return static_cast<int>(min_ugly_number);
    }
};