把只包含因子2,3和5的数称作丑数(ugly number)。例如6,8都是丑数,但14不是,因为它包含了因子7。习惯上我们把1作为第一个丑数。求按从小到大的顺序的第N个丑数。
int GetUglyNumber_Solution(int index) {
if (index<0) return 0;
if (index==1) return 1;
vector<int>k(index);
k[0]=1;
int num2=0,num3=0,num5=0;
for(int i=1;i<index;++i)
{
k[i]=min(k[num2]*2,min(k[num3]*3,k[num5]*5));
if(k[i]==k[num2]*2) num2++;
if(k[i]==k[num3]*3) num3++;
if(k[i]==k[num5]*5) num5++;
}
return k[index-1];
}
注解:建立一个大小为N的数组或容器,前十个丑数是1,2,3,4,5,6,8,9,10,12。先从1的2倍,3倍,5倍中选一个最小数,作为第二个丑数,然后从1的3倍,5倍,2的2倍中选择最小的数作为第三个丑数,然后从1的5倍,2的2倍,3的2倍中选一个最小的数作为下一个丑数......
每一个丑数都可以分解成一个或多个丑数的乘积。也可以看做之前已经存好的丑数的2倍或3倍或5倍的数。怎么选取前面哪一个数的2倍,哪一个数的3倍,哪一个数的5倍是关键。
从最小的丑数开始,记录他的2倍,3倍,5倍都是要取的,而且只能取一次,当某个丑数的2倍取过之后,就更新改丑数,更新为下一个比它大的丑数;当某个丑数的3倍取过之后,就更新丑数为下一个比他大的丑数;当某个丑数的5倍取过之后,就更新丑数为下一个比它大的丑数。更新之后,记录的仍为丑数的相对应的倍数。依次更新数组或容器,最后返回第N和元素即可。
网友评论