思路:我和想的方法和主流方法不一样,暴力打表。附上代码,难点在于确定指数范围。
题目描述
把只包含质因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。 class Solution { public: int GetUglyNumber_Solution(int index) { int uglynumber = 1;//丑数的本质是 2^k*3^j*5^i, int l = 0; long long a[100000] = {0};//所以暴力打表把Int范围内所有丑数存到a中 //为了确定i,j,k的范围,不能超过2^31-1,统一化log2为低的对数; double log5 = log(5)/log(2); double log3 = log(3)/log(2); for(int i=0;i<31;i++){ for(int j=0;j<31;j++) for(int k=0;k<31;k++){ if(i*log5+j*log3+k<31){ a[l++] = pow(2,k)*pow(3,j)*pow(5,i); } } } sort(a,a+l); uglynumber = a[index-1]; return uglynumber; } };