算法进阶——丑数

进阶——丑数"/>

算法进阶——丑数

题目

把只包含质因子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 hereif (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,5for (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);}
};