丑数的性质
一个较大的丑数必定是由一个较小的丑数*2/3/5得来的。
思路
我们可以由1这个最初的丑数,*2/3/5
得到三个新的丑数,然后再有新的丑数依次*2/3/5
得到新的丑数,最后再排序,然后返回当中第n个丑数。这种做法时间复杂度有点高,浪费了一些时间复杂度,它的本质还是打表,而且多了一个nlogn的排序时间,非常的慢。
优化一下,优化掉这个排序的过程,方法就是三指针法,我们直接按照从小到大的顺序求丑数就好了,为此我们需要三个指针,指向a[i]、a[j]、a[k],然后从a[i]2、a[j]3、a[k]*5当中挑出一个最小值,然后判断一下这三个数当中有没有跟这个值相同的,那么把这个指针后移一位,当我们用这种方式从小到大求了n个丑数之后就可以停止了,然后返回第n个丑数。相比于第一种方法,我们这种方法是On的,而且求到第n个丑数就立即停了下来没有多求。当然这种方法也可以直接用来打表的。
class Solution {
public:
int nthUglyNumber(int n) {
vector<int>a{1};
int i=0,j=0,k=0;
while(a.size()<n)
{
int temp=min(a[i]*2,min(a[j]*3,a[k]*5));
if(a[i]*2==temp)i++;
if(a[j]*3==temp)j++;
if(a[k]*5==temp)k++;
a.push_back(temp);
}
return a[n-1];
}
};