题目描述
编写一个程序，找出第 n 个丑数。
丑数就是质因数只包含 2, 3, 5 的正整数。
示例：
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明：
- 1 是丑数。
- n 不超过1690。
题目链接： https://leetcode-cn.com/problems/ugly-number-ii/
思路1
使用小根堆来做。丑数就是质因数只包含 2, 3, 5 的正整数，1 是丑数。所以我们先将 1 放入堆中，然后取出当前的堆顶元素 ans，将 ans*2、ans*3、ans*5 依次放入堆中。这样，我们第 i 循环得到的堆顶元素就是第 i 个丑数。因为生成丑数的过程可能出现重复的情况，例如 4*3 = 2*6，所以在将 ans*2、ans*3、ans*5 依次放入堆之前，还要判断这 3 个值是否在堆中出现过，如果没有出现过，则放入堆中，否则不放。可以使用 set 或者哈希表来记录元素是否出现过。代码如下：
class Solution {
public:
int nthUglyNumber(int n) {
priority_queue<long, vector<long>, greater<long>> q; // 要使用 long
set<long> s; // 要使用 long
s.insert(1);
q.push(1);
long ans = 1;
for(int i=1; i<=n; i++){
if(s.count(ans*2)==0){
q.push(ans*2);
s.insert(ans*2);
}
if(s.count(ans*3)==0){
q.push(ans*3);
s.insert(ans*3);
}
if(s.count(ans*5)==0){
q.push(ans*5);
s.insert(ans*5);
}
ans = q.top(); q.pop();
}
return ans;
}
};
- 时间复杂度：O(nlogn)
- 空间复杂度：O(n)
思路2
使用动态规划来做。使用 dp[i] 表示第 i+1 个丑数（i 从 0 开始），例如 dp[0] 表示第 1 个丑数。使用三个指针 p2, p3, p5，状态转移方程为 dp[i] = min(2*dp[p2], 3*dp[p3], 5*dp[p5])，i > 0，也就是 dp[i] 是 2*dp[p2]、3*dp[p3] 和 5*dp[p5] 之间的最小值。如果最小值是 2*dp[p2]，则 p2++；如果最小值是 3*dp[p3]，则 p3++；如果最小值是 5*dp[p5]，则 p5++。代码如下：
class Solution {
public:
int nthUglyNumber(int n) {
vector<long> dp(n);
dp[0] = 1;
int p2 = 0;
int p3 = 0;
int p5 = 0;
for(int i=1; i<n; i++){
dp[i] = min(2*dp[p2], min(3*dp[p3], 5*dp[p5]));
if(dp[i]==2*dp[p2]) p2++;
if(dp[i]==3*dp[p3]) p3++; // 不是 else if
if(dp[i]==5*dp[p5]) p5++; // 不是 else if
}
return dp[n-1];
}
};
- 时间复杂度：O(n)
- 空间复杂度：O(n)