丑数问题,力扣264,坑点
力扣链接
给你一个整数 n ,请你找出并返回第 n 个 丑数 。
丑数 就是质因子只包含 2、3 和 5 的正整数。
示例 1:
输入:n = 10
输出:12
解释:[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
示例 2:
输入:n = 1
输出:1
解释:1 通常被视为丑数。
正确源码:
class Solution {
public static int nthUglyNumber(int n) {
int p2=1;
int p3=1;
int p5=1;
int[] ugly=new int[n+1];
ugly[1]=1;
for(int i=2;i<=n;i++){
ugly[i]=Math.min(Math.min(3*ugly[p3],5*ugly[p5]),2*ugly[p2]);
if(ugly[i]==2*ugly[p2]){
p2++;
}
if(ugly[i]==3*ugly[p3]){
p3++;
}
if(ugly[i]==5*ugly[p5]){
p5++;
}
}
return ugly[n];
}
}
解读:
可以看出任何一个丑数都必定是前面的某一个比他小的丑数,乘以2或者3或者5得到的
因此只需要把所求丑数之前的所有丑数乘以2,3,5,然后找最小的即可
例如:最开始是求第二个丑数
2最小
然后是第三个丑数
3最小,第三个丑数是3
接着是第四个丑数
4最小,第四个丑数是4
这样做下去肯定是可以找到第n个丑数的,可是,是不是太复杂了,时间复杂度非常大
因此进行优化
首先,很明显丑数是递增的
因此在下面的图中
下一个丑数是5,他是5乘以某一个丑数得到的,10和15和20都是5乘以某一个丑数
但是在5没有被排好之前。是不可能轮到他们的,因为丑数是递增的数列,因此把他们乘出来,就是无用功,所以就可以拿一个指针p5来记录5乘到哪一个丑数了
对于其他因子2和3也是同理,一旦乘了某个丑数,对应的指针就加加
ugly[i]=Math.min(Math.min(3*ugly[p3],5*ugly[p5]),2*ugly[p2]);
if(ugly[i]==2*ugly[p2]){
p2++;
}else if(ugly[i]==3*ugly[p3]){
p3++;
}else if(ugly[i]==5*ugly[p5]){
p5++;
}
坑点:下面的代码是错的
class Solution {
public static int nthUglyNumber(int n) {
int p2=1;
int p3=1;
int p5=1;
int[] ugly=new int[n+1];
ugly[1]=1;
for(int i=2;i<=n;i++){
ugly[i]=Math.min(Math.min(3*ugly[p3],5*ugly[p5]),2*ugly[p2]);
if(ugly[i]==2*ugly[p2]){
p2++;
}else if(ugly[i]==3*ugly[p3]){
p3++;
}else if(ugly[i]==5*ugly[p5]){
p5++;
}
}
return ugly[n];
}
}
区别就在于,正确代码用的三个if,错误代码用的是else if。
错误代码过不了,放idea编译器里面发现会产生一些相同的重复丑数。
因为有可能2
×
\times
×ugly[p2]与3
×
\times
×ugly[p3]与5
×
\times
×ugly[p5]这三个中有至少两个相等,
假设是2
×
\times
×ugly[p2]和5
×
\times
×ugly[p5]相等,这个时候p2和p5都要同时加加
而用else if就只会加一次,所以会有重复的丑数