首先一个一个去验证是不是丑数一定不是最优的,直接将丑数一个一个求出来是时间复杂度最低的:
第一个丑数一定是1,
第二个丑数是前面所有丑数分别乘以2/3/5里面的大于已知最大丑数的最小值,即2
第三个丑数同理,在2/3/5 4/6/10里面大于2的最小值是3
第四个丑数同理,在2/3/5 4/6/10 6/9/15 里面大于3的最小值是4
慢慢发现越来越多的计算是可以省去的,比如一开始的丑数1和2,对应的2/3/5 4/6/10在后面的对比中一定会被忽略的,所以能不能想办法把无用的计算过滤掉。
设当前最大丑数是U
每次计算的结果中,有一部分是小于等于U,另一部分是大于U,那么大于U里面最小的M就是下一个丑数了,那么这个丑数是怎么得来的呢,我们不再用之前的思路将前面所有的丑数进行计算,而是选定三个数U2/U3/U5,那么下一个U就=min(2U2,3U3,5*U5)。
那么U2/U3/U5又是什么意思呢,我们定义U2乘以2后是下一个可能的丑数,U3乘以3后是下一个可能的丑数,U5乘以5后是下一个可能的丑数。所以每次求完丑数,都要将这三个“候选人”更新
class Solution {
public int getUglyNumber(int n) {
if(n<=0) return 0;
int[] res=new int[n];
res[0]=1;
int next=1;
int u2=0,u3=0,u5=0;
while(next<n){
int min=Math.min(res[u2]*2,Math.min(res[u3]*3,res[u5]*5));
res[next++]=min;
while(res[u2]*2<=min) u2++;
while(res[u3]*3<=min) u3++;
while(res[u5]*5<=min) u5++;
}
return res[n-1];
}
}
while(res[u2]2<=min) u2;
while(res[u3]*3<=min) u3;
while(res[u5]5<=min) u5;
应改为
if(res[u2]*2==min) u2;
if(res[u3]*3==min) u3;
if(res[u5]*5==min) u5;