题目描述
把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
题解
方法1：
最容易想到的就是依次判断每一个数是否为丑数，是则丑数个数加1，直到N。这种方法思路简单，实现容易，但效率极低。
//判断n是否为丑数
public boolean isUglyNumber(int n) { if(n==1 || n==2 || n==3 || n==5) return true; else if(n%2 == 0) return isUglyNumber(n/2); else if(n%3 == 0) return isUglyNumber(n/3); else if(n%5 == 0) return isUglyNumber(n/5); else return false; }
方法2：
按顺序计算出每一个丑数，直到N。由于丑数的因子仅由2、3、5组成，所以一个丑数可以由另一个丑数乘2、3或5得到，同时，我们需要以升序的方式来得到每一个新的丑数，因此，还需判断可以产生的新丑数中的最小值。
public int getUglyNumber_Solution(int index) {
if(index == 0)
return 0;
int a = 0, b = 0, c = 0; //a，b，c分别记录乘2，3，5的下标
int[] res = new int[index]; //保存前index 个丑数
res[0] = 1;
for(int i=1; i<index; i++)
{
res[i] = min(res[a]*2, res[b]*3, res[c]*5); //取可得到的最小丑数
if(res[i] == res[i-1]) //去重
i--;
if(res[i] == res[a]*2)
a ++;
else if(res[i] == res[b]*3)
b ++;
else
c ++;
}
return res[index-1];
}
public int min(int a, int b, int c)
{
int res = a;
if(res >b)
res = b;
if(res > c)
res = c;
return res;
}