题目描述
把只包含因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
这道题使用动态规划是比较易于理解的一种解法。思路如下:
丑数只包含因子2、3、5,那么反过来想,1、2、3、5这几个数组合相乘起来就能得到一个丑数,更进一步,一个丑数乘以2、3、5后可以得到另一个丑数,因此,我们可以通过已经存在的丑数推算出下一个丑数,由于要保证从小到大的序列,我们只需要每次都取最小值即可。
还有一个关键的地方,就是要知道2、3、5使用的次数,以保证不会出现重复的现象。
代码如下:
import java.util.*;
public class Solution {
public int GetUglyNumber_Solution(int index) {
if(index==0) return 0;
int[] factor={2,3,5};
int[] ugly=new int[index];//这里其实还可以对空间进行优化
ugly[0]=1;
int t2=0,t3=0,t5=0;//记录他们使用过的次数
for(int i=1;i<index;i++){
ugly[i]=Math.min(ugly[t2]*factor[0],Math.min(ugly[t3]*factor[1],ugly[t5]*factor[2]));
if(ugly[i]==ugly[t2]*factor[0])t2++;
if(ugly[i]==ugly[t3]*factor[1])t3++;
if(ugly[i]==ugly[t5]*factor[2])t5++;
}
return ugly[index-1];
}
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)