给你一个整数 n ，请你找出并返回第 n 个 丑数 。
丑数 就是只包含质因数 2、3 和/或 5 的正整数。
示例 1：
1
2
3
| 输入：n = 10
输出：12
解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
|
示例 2：
1
2
3
| 输入：n = 1
输出：1
解释：1 通常被视为丑数。
|
提示：
方法一：最小堆
初始时堆为空，首先将最小的丑数 1 加入堆，每次取出堆顶元素 x，则 x 是堆中最小的丑数，2x，3x，5x也是丑数，因此将 2x，3x，5x，加入堆中，但这会导致出现重复元素，为了避免出现重复元素，我们使用哈希表去重。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public int nthUglyNumber(int n) {
int[] factors = {2, 3, 5};
Set<Long> seen = new HashSet<>();
PriorityQueue<Long> heap = new PriorityQueue<>();
seen.add(1L);
heap.offer(1L);
int ugly = 0;
for(int i = 0; i < n; i++){
long curr = heap.poll();
ugly = (int) curr;
for(int factor : factors){
long next = curr * factor;
if(seen.add(next)){
heap.offer(next);
}
}
}
return ugly;
}
}
|
方法二：动态规划
在方法一中，我们存储了较多的丑数，导致空间复杂度较高。我们可以使用三个指针来指向最小的三个丑数。
定义数组 dp，dp[i] 表示第 i 个丑数，第 n 个丑数为 dp[n]，dp[1] = 1。
定义三个指针 p2，p3，p5，下一个丑数是当前指针指向的凑数乘以对应的质因数。下一个丑数分别为，2 * p2, 3 * p3, 5 * p5，我们取这三个数的最小值，然后将使用过的指针加一。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public int nthUglyNumber(int n) {
int[] dp = new int[n + 1];
dp[1] = 1;
int p2 = 1, p3 = 1, p5 = 1;
for(int i = 2; i <= n; i++){
int num2 = dp[p2] * 2, num3 = dp[p3] * 3, num5 = dp[p5] * 5;
dp[i] = Math.min(Math.min(num2, num3), num5);
if(dp[i] == num2){
++p2;
}
if(dp[i] == num3){
++p3;
}
if(dp[i] == num5){
++p5;
}
}
return dp[n];
}
}
|