题目：

 

 

解答：

方法一：优先级队列

 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 };