LeetCode 264.丑数II

给你一个整数 n ，请你找出并返回第 n 个 丑数 。

丑数 就是质因子只包含 2、3 和 5 的正整数。

示例 1：

输入：n = 10
输出：12
解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
示例 2：

输入：n = 1
输出：1
解释：1 通常被视为丑数。

提示：

1 <= n <= 1690

我们可以从最小的丑数开始，将其加入小顶堆中，每次取出堆顶的丑数后，将其乘丑数的质因子后再次加入堆中：

classSolution{public:intnthUglyNumber(intn){set<longlong>s;s.insert(1);s.insert(2);s.insert(3);s.insert(5);intans=0;for(inti=0;i<n;++i){ans=*s.begin();s.erase(ans);s.insert((longlong)ans*2);s.insert((longlong)ans*3);s.insert((longlong)ans*5);}returnans;}};

此算法时间复杂度为O(nlogn)，循环n次，每次循环时，从set中取出一个元素并加入三个元素，set中元素个数为O(3n)，即set的插入删除操作时间为O(logn)；空间复杂度为O(n)。