首页 > 其他 > 详细

面试题49. 丑数

时间:2020-05-09 19:23:10      阅读:107      评论:0      收藏:0      [点我收藏+]

题目:

技术分享图片

 

 

解答:

方法一:优先级队列

 1 class Solution {
 2     public int nthUglyNumber(int n) {
 3         PriorityQueue<Long> pq = new PriorityQueue<>();
 4         Set<Long> s = new HashSet<>();
 5         //初始化,放进堆和set,发现1要开Long数组才可以
 6         long[] primes = new long[]{2, 3, 5};
 7         for (long prime : primes) {
 8             pq.offer(prime);
 9             s.add(prime);
10         }
11         long num = 1;
12         for (int i = 1; i < n; i++) {
13             num = pq.poll();
14             //遍历三个因子
15             for (int j = 0; j < 3; j++) {
16                 if (!s.contains(num * primes[j])) {
17                     pq.offer(num * primes[j]);
18                     s.add(num * primes[j]);
19                 }
20             }
21         }
22         return (int) num;
23     }
24 }

 

 

方法二:动态规划

技术分享图片

 

 

 1 class Solution {
 2 public:
 3     int nthUglyNumber(int n) 
 4     {
 5         vector<int> res(n + 1, 0);
 6 
 7         res[0] = 1;
 8         int p2 = 0;
 9         int p3 = 0;
10         int p5 = 0;
11         for (int i = 1; i < n; i++)
12         {
13             // 更新数组
14             res[i] = std::min(res[p2]*2, std::min(res[p3]*3, res[p5]*5));
15             // 移动指针
16             if (res[i] == res[p2] * 2)
17             {
18                 p2++;
19             }
20             if (res[i] == res[p3] * 3) 
21             {
22                 p3++;
23             }
24             if (res[i] == res[p5] * 5) 
25             {
26                 p5++;
27             }
28         }
29 
30         return res[n - 1];
31     }
32 };

 

面试题49. 丑数

原文:https://www.cnblogs.com/ocpc/p/12859455.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!