参考《剑指Offer》
题目:
我们把只包含因子2、3和5的数称作丑数(Ugly Number)。求按从小到大的顺序的第1500个丑数。例如6、8都是丑数,但14不是,因为它包含因子7。习惯上我们把1当做是第一个丑数。
分析
常规解法
第一反应,我们肯定从1开始遍历,一直到找到第1500个丑数为止,如下:
bool isUgly(int number)
{ while (number%2==0) number = number/2; while (number%3==0) number = number/3; while (number%5==0) number = number/5; return (number==1)?true:false;
}
高效解法:
前面算法之所以效率低,是因为不管一个数是不是丑数都遍历了,我们要尝试找一个只需要计算丑数的方法。
首先,我们再次明确丑数的定义:
丑数是只包含因子2、3和5的数。
那么很容易我们就可以想到,位于前面的丑数,定然是后面的丑数的因子。比如2是4、6、30的因子,3是6、15、27、30的因子。
那么,我们可以通过前面的丑数乘以2、3、5来计算出后面的丑数。
而我们要解决的最主要的问题就是丑数的排序问题。
解决方法:每次找出生成的丑数中大于M的最小值。
首先,我们把已有的丑数都乘以2,找到其中第一个大于M的结果,记作M2。同样的方法乘以3、5,找到的结果记作M3、M5。
最终找到M2、M3、M5中的最小值,就是新生成的最大的丑数,记作新的M。
当然,如果每次都需要对丑数从头到尾的乘以和判断效率是很低的,我们可以用一个数T来记录M的下标。
比如T2,即为M2的下标,在它之前的每一个值乘以2都会小于M,在它之后的每一个值乘以2都会大于M。每次新生成M的时候我们再更新这个T2。
这样我们每次计算M2(乘以2后第一个大于M的数)的时候,只需要让T2后面的一个数乘以2即可了。
T3、T5的生成方式一样。
#代码
#include<iostream>using namespace std;int Min(int n1,int n2,int n3)
{int min=(n1<n2)?n1:n2;min=(min<n3)?min:n3;return min;
}int Solution(int n)
{if(n<=0)return 0;int u[n];u[0]=1;//1为第一个丑数int t2=0;//记录M2的下标int t3=0;int t5=0;for(int i=1;i<n;i++){while(u[t2]*2<=u[i-1])//查找到新的M2,即乘以2后第一个大于M的数t2++;while(u[t3]*3<=u[i-1])t3++;while(u[t5]*5<=u[i-1])t5++;int min=Min(u[t2]*2,u[t3]*3,u[t5]*5);u[i]=min;}return u[n-1];
}int main()
{cout<<Solution(1500)<<endl;return 0;
}