设计一个算法，找出只含素因子2，3，5 的第 n 大的数。
符合条件的数如：1, 2, 3, 4, 5, 6, 8, 9, 10, 12...
看到题的第一个想法一直向下枚举 直到找到第N个数
我的思路是 ：每一个丑数都是由一个丑数乘2乘3乘5得来的，可以把第一个丑数也就是1放进优先队列中，然后进行N次操作每次取出队头然后把队头
的二倍，三倍，五倍入队，注意的是队列中可能会有重复的数所以要判断是不是重复的数
codelint提交代码如下
class Solution { public: /* * @param n an integer * @return the nth prime number as description. */ int nthUglyNumber(int n) { // write your code here priority_queue<long long,vector<long long >,greater<long long > > s; s.push(1); long long last = 0; long long t=0; n--; while(n--) { t = s.top(); while(t == last) { t = s.top(); s.pop(); } last = t; s.push(t*2); s.push(t*5); s.push(t*3); } while(t == last) { t = s.top(); s.pop(); } return t; } }; C++调试代码如下
#include <iostream> #include <functional> #include <queue> using namespace std; int main() { priority_queue<long long,vector<long long >,greater<long long > > s; s.push(1); long long last = 0; int n; cin>>n; long long t=0; n--; while(n--) { t = s.top(); while(t == last) { t = s.top(); s.pop(); } last = t; s.push(t*2); s.push(t*5); s.push(t*3); } while(t == last) { t = s.top(); s.pop(); } cout<<t<<endl; return 0; }
