263. 丑数
思路
- 首先,丑数必须是正整数,因此对于
n<1
都可以直接返回 false; - 对于
n >= 1
,如果 n 能够被 2/3/5 整除,说明它们是丑数。
代码
class Solution {
public:
bool isUgly(int n) {
// ugly只能是正整数
if(n < 1) return false;
vector<int> factors = {2, 3, 5};
for(int i=0; i<=2; ++i){
while(n % factors[i] == 0){
n /= factors[i];
}
}
return n == 1;
}
};
264. 丑数 II
方法一:最小堆
思路
- 要得到第 n 个丑数,可以使用最小堆实现。
- 初始化堆为空,首先将最小的丑数 1 加入。每次取出堆顶元素 x ,则 x 是堆中最小的丑数,2x、3x、5x 必然也是丑数,因此将它们也加入最小堆。
- 但是上述做法会出现重复元素,为了避免这种情况,用哈希集合去重,避免相同元素多次加入堆。
- 在排除重复元素的情况下,第 n 次从最小堆中取出的元素即为第 n 个丑数。
代码
class Solution {
public:
int nthUglyNumber(int n) {
vector<int> factor = {2, 3, 5};
priority_queue<long, vector<long>, greater<long>> heap;
unordered_set<long> s;
// 先把丑数 1 加入
s.insert(1L);
heap.push(1L);
long cur;
for(int i=0; i<n; ++i){
cur = heap.top();
heap.pop();
for(int f : factor){
// 依次计算 2x 3x 5x
long temp = cur * f;
// s中没有temp 将其存入
if(!s.count(temp)){
s.insert(temp);
heap.push(temp);
}
}
}
return (int)cur;
}
};
方法二:动态规划(三指针法)
思路
-
方法一使用最小堆,会预先存储较多的丑数,维护最小堆的过程也导致时间复杂度较高。可以使用动态规划的方法进行优化。
-
定义数组 dp,其中 dp[i] 表示第 i 个丑数,则 dp[n] 为这道题的答案。其中,dp[1] = 1。
-
剩余的丑数我们可以通过三个指针 p2 、p3、p5 计算得到。pi 的含义是有资格同 i 相乘的最小丑数的位置。这里资格指的是:如果一个丑数nums[pi]通过乘以 i 可以得到下一个丑数,那么这个丑数nums[pi]就永远失去了同 i 相乘的资格,我们把pi++,让 nums[pi] 指向下一个丑数即可。
-
举例说明:
一开始,丑数只有{1},1 可以同 2,3,5相乘,取最小的 1×2=2 添加到丑数序列中。
现在丑数中有{1,2},在上一步中,1 已经同 2 相乘过了,所以今后没必要再比较 1×2 了,因此认为 1 失去了同 2 相乘的资格。
现在 1 有与 3,5 相乘的资格,2 有与 2,3,5 相乘的资格,但是 2×3 和 2×5 肯定比 1×3 和 1×5 大,因此没必要比较。所以我们只需要比较 1×3,1×5,2×2。
依此类推,每次我们都分别比较有资格同 2,3,5 相乘的最小丑数,选择最小的那个作为下一个丑数,假设选择到的这个丑数是同 i(i=2,3,5)相乘得到的,所以它失去了同 i 相乘的资格,把对应的pi++,让 pi 指向下一个丑数即可。
代码
class Solution {
public:
int nthUglyNumber(int n) {
vector<int> dp(n+1);
dp[1] = 1;
int p2 = 1, p3 = 1, p5 = 1;
for(int i=2; i<=n; ++i){
int num2 = 2 * dp[p2];
int num3 = 3 * dp[p3];
int num5 = 5 * dp[p5];
dp[i] = min(min(num2, num3), num5);
// 确定dp[i]是由哪个数字生成的
if(dp[i] == num2) p2++;
if(dp[i] == num3) p3++;
if(dp[i] == num5) p5++;
}
return dp[n];
}
};
1201. 丑数 III
方法:二分查找 + 容斥原理
思路
-
首先要注意的是,这道题和前两题对于“丑数”的定义并不相同。这里不能直接枚举丑数 x(三指针法),因为 x 太大了,会导致超时。
-
这道题是 878. 第 N 个神奇数字 的升级版。把两个数改为了三个数,难度更高。与 878 题相比,这题的只需要修改求小于等于 x 的丑数个数的函数,二分查找部分一模一样。建议先复习 878 题,下面附上该题的思路图。
-
把小于等于 x 的 a 的倍数、b 的倍数、c 的倍数组成的集合分别叫做 A、B、C ,小于等于 x 的丑数相当于集合 A∪B∪C ,集合的元素个数为 ∣A∪B∪C∣,由 容斥原理可得:
∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣+∣A∩B∩C∣
-
因此,小于等于 x 的丑数的个数为:
x/a + x/b + x/c - x/lcm_a_b - x/lcm_b_c - x/lcm_a_c + x/lcm_a_b_c
。可以使用最小公倍数函数std::lcm
。 -
接下来通过二分搜索,不断缩小边界,直到某个位置所对应的数恰好包含了 n 个丑数因子为止。
代码
class Solution {
public:
using ll = long long;
ll nthUglyNumber(ll n, ll a, ll b, ll c) {
ll lcm_a_b = std::lcm(a, b), lcm_a_c = std::lcm(a, c), lcm_b_c = std::lcm(b, c);
ll lcm_a_b_c= std::lcm(lcm_a_b, c);
// 最小的丑数必然是a、b、c的最小值
ll left = min(min(a, b), c);
ll right = n * left;
while(left + 1 < right){
ll mid = (left + right) / 2;
if(mid/a + mid/b + mid/c - mid/lcm_a_b - mid/lcm_a_c - mid/lcm_b_c + mid/lcm_a_b_c < n){
left = mid;
}
else right = mid;
}
return right;
}
};
313. 超级丑数
方法:“多路归并”
思路
-
这道题其实是
264. 丑数 II
的进阶,前者固定使用三个指针,分别对应于 2、3、5,而这道的primes数组长度不固定,因此使用指针数组来对应 primes 的每一个值。 -
第一个丑数一定是 1,而「往后产生的丑数」都是基于「已有丑数」而来(使用「已有丑数」乘上「给定质因数」primes[i] )。具体过程如图所示。文章来源:https://www.toymoban.com/news/detail-646723.html
文章来源地址https://www.toymoban.com/news/detail-646723.html
- 显然,我们需要每次取值最小的一个,然后让指针后移(指向下一个丑数),不断重复这个过程,直到找到第 n 个丑数。
- 另外,由于我们每个指针移动和 dp的构造,都是单调递增,因此可以通过与 dp[i-1] 进行比较来实现去重,而无须引用 Set 结构。
代码
class Solution {
public:
long nthSuperUglyNumber(int n, vector<int>& primes) {
int len = primes.size();
// 指针数组
vector<long> ptr(len, 1);
vector<long> dp(n+1, 0);
dp[1] = 1;
for(int i=2;i<=n;++i){
int flag = 0;
dp[i] = primes[0] * dp[ptr[0]];
for(int j=0; j<len; ++j){
long cur = primes[j] * dp[ptr[j]];
if(cur < dp[i]){
flag = j;
dp[i]= cur;
}
}
ptr[flag]++;
// 如果当前值和上一个丑数一样,那么跳过该丑数
if(dp[i] == dp[i-1]) i--;
}
return dp[n];
}
};
总结
- 以上是丑数的所有相关题目,丑数的定义并不固定,因此需要仔细理解题意后再开始计算。
- 对于
263. 丑数
,运用简单的数学思想即可解决; - 对于
264. 丑数II
,使用了最小堆和动态规划(即三指针的方法),但是最小堆的方法比较费时,更推荐方法二; - 对于
1201. 丑数III
,与一般的丑数定义不同,是 878. 第 N 个神奇数字 的升级版,使用了二分查找和容斥原理; - 对于
313.超级丑数
,是264. 丑数II
的升级版,将三指针方法扩展为多指针即可求解,也可以理解为多路归并法。
参考资料
- 丑数 II 官方题解
- 三指针方法的理解方式
- 313. 超级丑数:【宫水三叶】一题双解 :「优先队列」&「多路归并」
到了这里,关于【LeetCode】丑数题目合辑的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!