【剑指offer-c++】jz49:丑数-爱代码爱编程
题目描述
描述:把只包含质因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第 n个丑数。
数据范围:0≤n≤2000。
要求:空间复杂度 O(n) , 时间复杂度 O(n)。
输入:7
返回值:8
解题思路
丑数:最直观的想法是,暴力质因数分解,由于此处质因子只有2、3、5,故与原始质因数分解写法有些许不同。首先编写isUgly函数用于判断数n是否为丑数,由于1、2、3、4、5、6均是丑数,故若index小于等于6,则直接返回index即可,反之记录当前丑数数量num为6,再从7开始遍历,如果当前数是丑数,则对应丑数数量num加一,再判断丑数数量num是否等于给定个数index,如果是则记录结果并返回。(超时)
//判断是否为丑数 与原始的质因数分解不同
bool isUgly(int n)
{
while(n%2==0) n/=2;
while(n%3==0) n/=3;
while(n%5==0) n/=5;
return n==1;
}
int GetUglyNumber_Solution(int index)
{
// 1 2 3 4 5 6均是丑数
if(index<=6)
return index;
//记录第一个丑数
int num=6;
//记录对应结果
int result;
for(int i=7;;i++)
{
//如果是丑数则丑数数量加一
if(isUgly(i))
num++;
//如果数量等于待求解的则记录结果
if(num==index)
{
result=i;
break;
}
}
return result;
}
优化:上述方法很明显超时,故我们需要找出方法对其进行优化。由于质因子只有2、3、5的为丑数,且所需的n个丑数是按从小到大的顺序进行排列的,假设我们知道前n-1个丑数,那么我们只需将前n-1个丑数每一个分别乘以2、3、5即可得到新的丑数,然后从中检查出与前n-1个丑数不重复的且最小的丑数即可得到第n个丑数。但是这样做法下的时间复杂度仍然很高,所以我们继续想办法优化。根据规律可以知道,第一个丑数为1,将其分别乘以2、3、5,然后取最小的2,由于2是由1乘以2得到的,所以下一个因为乘以2得到的丑数必然是根据2得到的,这时我们就可以根据此单调性规律来设置三指针。具体做法如下:使用res[i]表示第i个丑数,其中第一个丑数是1,分别使用指针p2、p3、p5表示下一个丑数可以根据res[p2]*2、res[p3]*3、res[p5]*5得到,首先根据三指针得到最小的丑数,然后判断该丑数是由哪一个得到的,并将对应的指针后移,当数组长度小于index时一直执行直至相等,最后返回res最后一个元素即可。
int GetUglyNumber_Solution(int index)
{
// 1 2 3 4 5 6均是丑数
if(index<=6)
return index;
//用于记录丑数
vector<int> res;
//用于记录最小值
int minx;
//第一个丑数为1
res.push_back(1);
//三指针 分别标记下一个丑数可以根据 res[i]*2 res[j]*3 res[k]*5得到
int p2=0,p3=0,p5=0;
//当数组长度小于index一直执行直至相等
while(res.size()<index)
{
//取最小值
minx=min({res[p2]*2,res[p3]*3,res[p5]*5});
res.push_back(minx);
if(minx==res[p2]*2)
p2++;
if(minx==res[p3]*3)
p3++;
if(minx==res[p5]*5)
p5++;
}
return res[res.size()-1];
}