设计一个算法,找出只含素因子2,3,5 的第 n 小的数。
符合条件的数如:1, 2, 3, 4, 5, 6, 8, 9, 10, 12...
样例
如果n = 9
, 返回10
暴力遍历
暴力遍历,判断一个数是否只有2,3,5的素因子,如果是,放入容器,计数加1,直到找到第n个然后输出就行了,写起来也简单:
bool IsUgly(int n)
{
while(n%2==0) //可以被2整除的话就除以2,下同
{
n/=2;
}
while(n%3==0)
{
n/=3;
}
while(n%5==0)
{
n/=5;
}
if(n==1) //如果最后除完得到的是1,说明确实只含有2,3,5的因子,则是丑数
return true;
else
return false;
}
int nthUglyNumber(int n)
{
int num=1; //从1开始遍历
int index=0; //记录已找到丑数的个数
while(1)
{
if(IsUgly(num)) index++; //如果是丑数,那么计数器加1
if(index==n) return num; //如果是第n个,那么就返回
num++;
}
}
不出意料大数据的时候时间会超出限制。
找规律
这种题说起来都是数学题,只要能找出规律来就能减少运算量。
注意到这样一个现象:一个丑数乘以2,3,5的话肯定还是丑数,也就是说丑数可以由丑数生成,我们如果只有一个初始值1,那么还是可以生成丑数。我们把丑数序列记作res.
第二个丑数应该是: min(res[1]*2,res[1]*3,res[1]*5); min(2,3,5)=2
第三个丑数应该是: min(res[2]*2,res[1]*3,res[1]*5); min(4,3,5)=3
第三个丑数应该是: min(res[2]*2,res[2]*3,res[1]*5); min(4,6,5)=4
每次更新只更新一个数十为了保证这样更新的数一定是有序的,我们用了三个指针在这里,2,3,5这三个因子保持不动,哪一个因子作用的数被采纳,我们就把对应的指针+1,移到下一个数上,这样虽然会有重复计算(因为一般情况下我们每次都只更新一个指针),但是可以保证每次更新的都是最小的丑数。如果一个循环中算出了两个最小值,那么对应的两个指针都++,下面是当n等于9的时候的打印日志:
对应的代码需要注意的是:判断哪个指针指向最小值的if之间不要用else!
int nthUglyNumber(int n) {
int start=1;
vector<int> res; //存放结果
res.push_back(start); //第一个数先放进去
if(n==1) //处理特殊情况
return 1;
int index=1; //序列号
int p2,p3,p5; //记录的是当前乘以2,3,5的数的索引。
p2=p3=p5=0; //所以初始化为1,每次枚举三个数
while(index<n)
{
res.push_back(min3(2*res[p2],3*res[p3],5*res[p5])); //每次把最小的放入数组
cout<<2*res[p2]<<" "<<3*res[p3]<<" "<<5*res[p5]<<endl;
if(2*res[p2]==*(res.end()-1)) p2++;
//如果刚放入的是2*res[p2],就把p2++,下次就用下一个数乘以2了。
if(3*res[p3]==*(res.end()-1)) p3++;
if(5*res[p5]==*(res.end()-1)) p5++;
//上面三个if之间不要用else,因为可能存在多个最小值,都需加1。
index++; //索引加1,
}
return *(res.end()-1); //返回最后一个数
// write your code here
}
利用set暴力去重排序。
这样也是可以的,不过计算量也是挺大的,因为还是有大量的重复计算。我就不写了。
网友评论