【LeetCode每日一题】264. 丑数 II
题目：给你一个整数 n ，请你找出并返回第 n 个 丑数 。
丑数 就是只包含质因数 2、3 和/或 5 的正整数。
示例 1：
代码语言：javascript复制输入：n = 10
输出：12
解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
题解：
解法1：直接生成所有数据，取出对应的元素即可。如果采用递归，肯定会TL，这里采用迭代。
代码语言：javascript复制class Solution {
public:
int nthUglyNumber(int n) {
vector<int> data;
int i = 1;
for (long long i=1; i<INT_MAX; i*=2) {
for (long long j=i; j<INT_MAX; j*=3) {
for (long long k=j; k<INT_MAX; k*=5) {
data.push_back(k);
}
}
}
sort(data.begin(), data.end());
return data[n-1];
}
};
解法2：堆与去重
类似于二叉树的层次遍历，入队操作是以小到大，从堆中出来的每次是最小的，当出来n次时，则结束。
注意：入堆时有重复元素就不要入堆了，因为这样会多算。
代码语言：javascript复制class Solution {
public:
typedef long long LL;
int nthUglyNumber(int n) {
set<LL> s;
priority_queue<LL, vector<LL>, greater<LL>> pq;
s.insert((LL)1);
pq.push((LL)1);
int ans = 1;
vector<int> factor{2, 3, 5};
while (n--) {
LL cur = pq.top(); pq.pop();
ans = (int)cur;
// [2,3,5]
for (auto x : factor) {
LL mu = cur*x;
if (s.count(mu)) continue;
s.insert(mu);
pq.push(mu);
}
}
return ans;
}
};
解法3：动态规划及三指针。
dp[i]表示第i个丑数，那么dp[i]的转移来自于：
代码语言：javascript复制dp[p2]*2、dp[p3]*3、dp[p5]*5
实现：
代码语言：javascript复制class Solution {
public:
typedef long long LL;
int nthUglyNumber(int n) {
vector<LL> dp(n 1, 0x3f3f3f3f);
dp[1] = 1;
int p2 = 1, p3 = 1, p5 = 1;
for (int i = 2; i <= n; i ) {
LL n2 = dp[p2] * 2, n3 = dp[p3] * 3, n5 = dp[p5] * 5;
dp[i] = min(min(n2, n3), n5);
if (dp[i] == n2) {
p2 ;
}
if (dp[i] == n3) {
p3 ;
}
if (dp[i] == n5) {
p5 ;
}
}
return dp[n];
}
};
本节完~
