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){setlonglongs;s.insert(1);s.insert(2);s.insert(3);s.insert(5);intans0;for(inti0;in;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)。