题目描述：
把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
解题思路：
所谓一个数m是另一个数n的因子，是指n能被m整除，也就是n%m==0。据此，本题有以下两种解法：
方法一：逐个判断每个整数是不是丑数
丑数只能被2、3、5整除，也就是说，如果一个数能被2整除，就连续除以2；如果能被3整除，就连续除以3；如果能被5整除，就连续除以5；如果最后得到的是1，那么这个数就是丑数，否则不是。由此，按照顺序依次判断每个整数，并进行计数，就可以找到第N个丑数。这种方法简单直观，但是需要判断每一个整数，不够高效。
方法二：创建数组保存已经找到的丑数，用空间换时间
为了提高效率，我们可以只计算丑数，不在非丑数上浪费时间。根据丑数的定义，丑数应该是另一个丑数乘以2、3或者5的结果（1除外）。因此，我们可以创建一个数组，里面保存的是排好序的丑数，每一个丑数都可以由前面的丑数乘以2、3或者5得到。
这个思路的关键在于如何保证数组里的丑数都是排好序的，也就是每次怎样生成新的丑数。对乘以2而言，肯定存在某个丑数M2，排在它之前的所有丑数乘以2都会小于已有的最大丑数，在它之后的丑数乘以2都会比他大。而对乘以3和5而言，也存在同样的M3和M5，因此只需要维护三个索引值即可判断下一次生成的丑数应该是多少。
编程实现（Java）：
public class Solution {
public int GetUglyNumber_Solution(int index) {
/*思路：两种方法：
（1）依次判断丑数只包含质因子2,3,5，连续除以2，连续处于3，连续除以5，最终得到1说明是丑数
（2）空间换时间，丑数应该是另外一个丑数乘以2,3,5的结果，因此用一个数组保存排好序的丑数，依次计算下一个丑数 */
if(index<1)
return 0;
int[] pUglyNumbers=new int[index]; //依次保存第n个丑数
pUglyNumbers[0]=1; //第一个丑数是1
int pMultiply2=0,pMultiply3=0,pMultiply5=0;
for(int i=1;i<index;i++){
int min=getMin(pUglyNumbers[pMultiply2]*2,pUglyNumbers[pMultiply3]*3,
pUglyNumbers[pMultiply5]*5);
pUglyNumbers[i]=min;
while(pUglyNumbers[pMultiply2]*2<=min)
pMultiply2++;
while(pUglyNumbers[pMultiply3]*3<=min)
pMultiply3++;
while(pUglyNumbers[pMultiply5]*5<=min)
pMultiply5++;
}
return pUglyNumbers[index-1];
}
public int getMin(int a,int b,int c){
int min=a>b?b:a;
return c<min?c:min;
}
}