丑数

题目：

把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

解题思路：

1.已有的丑数按顺序存放在数组中，对乘2而言，肯定存在某一个丑数T2，排在它之前的每一个丑数乘2得到的结果都会小于已有的最大丑数，在它之后的每一个丑数乘2得到的结果都会太大。因此，我们只需记下这个丑数的位置，同时每次生成新的丑数的时候，更新这个T2。乘3和乘5同理。

java实现：

public class Solution { public int GetUglyNumber_Solution(int index) { if(index < 7) return index; int [] uglyNum = new int[index]; //存放丑数 uglyNum[0] = 1; //习惯上我们把1当做是第一个丑数 int t2 = 0, t3 = 0, t5 = 0; //初始都在位置0 for(int i = 1; i < index; i ++){ uglyNum[i] = Math.min(uglyNum[t2] * 2,Math.min(uglyNum[t3] * 3, uglyNum[t5] * 5)); //当前丑数为乘2，乘3和乘5中的最小者 if(uglyNum[t2] * 2 == uglyNum[i]) //如果当前丑数等于T2，则更新T2 t2++; if(uglyNum[t3] * 3 == uglyNum[i]) //如果当前丑数等于T3，则更新T3 t3++; if(uglyNum[t5] * 5 == uglyNum[i]) //如果当前丑数等于T5，则更新T5 t5++; } return uglyNum[index - 1]; //数组下标从0开始 } }