LeetCode264 丑数II

链接: https://leetcode-cn.com/problems/find-the-duplicate-number/

题面

给你一个整数 n ,请你找出并返回第 n 个 丑数 。
丑数 就是只包含质因数 2、3 或 5 的正整数。

解法

这道题有两种不同的解法,比较容易想到是用一个优先队列
每次取出最小的数分别乘以2、3 和 5 再加入队列
直到取到第 n 个

还有一种dp的解法,这里贴一个在题解中看到的比较好的解释
例如 n = 10, primes = [2, 3, 5]。 打印出丑数列表:1, 2, 3, 4, 5, 6, 8, 9, 10, 12
首先一定要知道,后面的丑数一定由前面的丑数乘以2,或者乘以3,或者乘以5得来。例如,8,9,10,12一定是1, 2, 3, 4, 5, 6乘以2,3,5三个质数中的某一个得到。

这样的话我们的解题思路就是:从第一个丑数开始,一个个数丑数,并确保数出来的丑数是递增的,直到数到第n个丑数,得到答案。那么问题就是如何递增地数丑数?

观察上面的例子,假如我们用1, 2, 3, 4, 5, 6去形成后面的丑数,我们可以将1, 2, 3, 4, 5, 6分别乘以2, 3, 5,这样得到一共6*3=18个新丑数。也就是说1, 2, 3, 4, 5, 6中的每一个丑数都有一次机会与2相乘,一次机会与3相乘,一次机会与5相乘,来得到更大的一个丑数。一共有18次机会形成18个新丑数。

这样就可以用三个指针,

1
2
3
pointer2, 指向1, 2, 3, 4, 5, 6中,还没使用乘2机会的丑数的位置。该指针的前一位已经使用完了乘以2的机会。
pointer3, 指向1, 2, 3, 4, 5, 6中,还没使用乘3机会的丑数的位置。该指针的前一位已经使用完了乘以3的机会。
pointer5, 指向1, 2, 3, 4, 5, 6中,还没使用乘5机会的丑数的位置。该指针的前一位已经使用完了乘以5的机会。

下一次寻找丑数时,则对这三个位置分别尝试使用一次乘2机会,乘3机会,乘5机会,看看哪个最小,最小的那个就是下一个丑数。最后,那个得到下一个丑数的指针位置加一,因为它对应的那次乘法使用完了。

这里需要注意下去重的问题,如果某次寻找丑数,找到了下一个丑数10,则pointer2和pointer5都需要加一,因为5乘2等于10, 2乘5也等于10,这样可以确保10只被数一次。
很巧妙的解法,同时也降低了时间复杂度,在后续更复杂的找丑数问题中也可以进行推广

代码

优先队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
int nthUglyNumber(int n) {
vector<int> primes{2, 3, 5};
priority_queue<int, vector<int>, greater<int>> pq;
pq.push(1);
for (int i: primes) {
pq.push(i);
}
int index = 0, a, maxv = primes.back();
while(index < n) {
a = pq.top();
while(pq.size() && pq.top() == a) {
pq.pop();
}
index++;
if (index == n) return a;
for (int i: primes) {
if ((long long) i * a > INT_MAX) continue;
pq.push(i * a);
}
}
return 0;
}
};

动态规划

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 p1 = 1, p2 = 1, p3 = 1;
vector<int> dp(n + 1);
dp[1] = 1;
for (int i = 2; i <= n; i++) {
int temp = min(dp[p1] * 2, dp[p2] * 3);
temp = min(temp, dp[p3] * 5);
dp[i] = temp;
if (temp == dp[p1] * 2) {
p1++;
}
if (temp == dp[p2] * 3) {
p2++;
}
if (temp == dp[p3] * 5) {
p3++;
}
}
return dp[n];
}
};