丑数的标准定义：丑数 就是只包含质因数 2、3 和/或 5 的正整数， 1为最小的丑数
在该定义的基础上，对质因数和求解目标进行调整，形成了leetcode中常见的丑数问题； 因为涉及质数，因此丑数问题中往往也需要一定的质数算法思想。基本的考察问题为：
- 判断是否为丑数
- 计算第n个丑数
- 改变质因数或者拓展丑数定义，计算第n个丑数 其中计算第n个丑数，常用思路为 排序 + 存储
- 基于优先队列/堆进行实现
- 基于动态规划+多指针进行实现
给你一个整数 n ，请你判断 n 是否为 丑数 。如果是，返回 true ；否则，返回 false 。 丑数 就是只包含质因数 2、3 和/或 5 的正整数 **1 通常被视为丑数。 **
- 简单的数学判断题目
- 可以利用循环相除进行余数判断即可
- 需要注意对特殊情况： 0的判断
class Solution {
public:
bool isUgly(int n) {
int factors[3] = {2, 3, 5};
int i = 0;
while (n > 0 && i < 3) {
if (n % factors[i] == 0) {
n /= factors[i];
}
else {
i++;
}
}
if (n == 1) return true;
return false;
}
};给你一个整数 n ，请你找出并返回第 n 个 丑数 。 丑数 就是只包含质因数 2、3 和/或 5 的正整数。
- 承接[LC263.], 本题需要搜索第n个丑数，最简单的方法为暴力遍历，取第n个数
- 从算法角度考虑，进行搜索优化：
- 使用优先队列进行处理
- 利用最小堆进行中间丑数维护，每次将2、3、5的倍数插入堆中，
- 进行n次出堆操作，最后一次出堆即为第n个丑数
- 堆维护了数字的有序性，每次出堆即得到升序的第i个丑数
- 由于过程中可能出现重复值，使用哈希表进行去重控制
- 时间复杂度 O(NlogN)
- 空间复杂度 O(N)
class Solution {
public:
int nthUglyNumber(int n) {
// 使用long 避免溢出
priority_queue<long, vector<long>, greater<long>> q;
int ugly = 1;
vector<int> factors = {2, 3, 5};
unordered_set<long> seen;
q.push(ugly);
for (int i = 0; i < n; i++) {
long cur = q.top();
ugly = cur;
q.pop();
for (auto p : factors) {
if (!seen.count(p * cur)) {
q.push(p * cur);
seen.insert(p*cur);
}
}
}
return ugly;
}
};- 基于动态规划的思想进行搜索：
dp[i]定义： 第i个丑数- 状态转移：
dp[i] = min(dp[p1]*2, dp[p2]*3, dp[p3]*5)， 2 <= i <= n - 其中
p1p2p3为三种因子的数量指针： 代表的是第几个数的2倍、第几个数 3 倍、第几个数 5 倍 - 本质上计算与最小堆的入堆/出堆逻辑相同：
- 小顶堆的方法是先存再排，dp的方法则是先排再存
- 初始化：
dp[1] = 1p1 = p2 = p3 = 1
- 时间复杂度 O(N) 空间复杂度 o(N)
- 本题关键：
如何维护有序性三指针 + 动态规划
class Solution {
public:
int nthUglyNumber(int n) {
// 使用long 避免溢出
vector<long> dp(n + 1);
dp[1] = 1;
int p1 = 1;
int p2 = 1;
int p3 = 1;
for (int i = 2; i <= n; i++) {
dp[i] = min(dp[p1]*2, min(dp[p2]*3, dp[p3]*5));
// 各个因子指针进行同步比较更新
if (dp[i] == dp[p1]*2) {
p1++;
}
if (dp[i] == dp[p2]*3) {
p2++;
}
if (dp[i] == dp[p3]*5) {
p3++;
}
}
return dp[n];
}
};超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数 1 是任何给定 primes 的超级丑数。
输入: n = 12, primes = [2,7,13,19]
输出: 32
解释: 给定长度为 4 的质数列表 primes = [2,7,13,19]，前 12 个超级丑数序列为：[1,2,4,7,8,13,14,16,19,26,28,32] 。
- 与计算第n个丑数的问题的区别在于，本题是一个质数列表，是对质数做了扩展，但是丑数的本质没有变：
- 1 是任何给定 primes 的超级丑数。
- 仍然采用最小堆或者多指针的动态规划进行实现
class Solution {
public:
int nthSuperUglyNumber(int n, vector<int>& primes) {
vector<int> ps(primes.size(), 1);
vector<int> dp(n+1);
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[ps[0]] * primes[0];
for (int j = 1; j < primes.size(); j++) {
dp[i] = min(dp[ps[j]] * primes[j], dp[i]);
}
for (int j = 0; j < primes.size(); j++) {
if (dp[i] == dp[ps[j]] * primes[j]) {
ps[j]++;
}
}
}
return dp[n];
}
};给你四个整数：n 、a 、b 、c ，请你设计一个算法来找出第 n 个丑数。 丑数是可以被 a 或 b 或 c 整除的 正整数 。
输入：n = 3, a = 2, b = 3, c = 5
输出：4
解释：丑数序列为 2, 3, 4, 5, 6, 8, 9, 10... 其中第 3 个是 4。
-
注意： 此题中1 不是默认的丑数，此处为广义上的丑数
-
由于a b c因子是输入的， 那么该题目的范围应该是比较大的
-
区别与上面两题中标准的丑数定义，本题无法用上面的dp、堆来解题，一方面时间复杂度还是比较高，另一方面存在临界问题
-
本题的思路是采用二分法+数学分析来完成的
- 查找第n个丑数，我们可以通过数学分析得到[0,X]范围内的丑数数量：
X/a + x/b + X/c - X/lcm(a,b) - X/lcm(a, c) - X/lcm(b,c) + X/lcm(a,b,c)- 即计算被因子整除的数量，其中要避免重复计算的情况，因此需要计算因子间的最小公倍数，根据容斥原理得到实际的丑数数量
- 计算最小公倍数：
lcm(a,b) - 计算最大公约数：
gcd(a,b)
-
关键点：
最小公倍数+丑数数量分析
class Solution {
public:
int nthUglyNumber(int n, int a, int b, int c) {
long left = 0;
long right = 2e9;
// 最小公倍数计算
// 统一使用long 避免乘法计算溢出
long la = a;
long lb = b;
long lc = c;
long lab = lcm(la, lb);
long lac = lcm(la, lc);
long lbc = lcm(lb, lc);
long labc = lcm(lab, lc);
while ( left < right) {
long mid = left + (right - left) / 2;
long sum = mid / la + mid / lb + mid / lc - mid / lab - mid/lac -mid/lbc + mid/labc;
if (sum < n) {
left = mid + 1;
}
else {// sum >= n
right = mid;
}
}
return left;
}
};