即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

lintcode 4.丑数 II(优先队列)

编程语言 dlnumk 15℃ 0评论

设计一个算法,找出只含素因子235 的第 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,greater > 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 
#include 
#include 

using namespace std;

int main()
{
 priority_queue,greater > 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<





转载请注明:CodingBlog » lintcode 4.丑数 II(优先队列)

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情