【题目描述】把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
【题目解释】原题中的描述并不确切，这里做一下详细些的解释。原题的本意是，丑数是可以通过不断的除2、3、5，最后等于1的数字。其中2、3、5可以重复出现。即丑数可以通过2、3、5的乘积来表示。所以，虽然8包含因子4，但依旧符合丑数的定义。 6 = 2*3； –> 丑数 8 = 2*2*2；–> 丑数 14 = 2*7； –> 不是丑数
【解题思路】 //1. 观察到丑数最终都可以表示为若干个2、3、5乘积的形式。 //2. 所以下一个丑数可以用某个丑数分别乘上2、3、5来表示。 //3. 具体是从当前已知的丑数数组中从小到大遍历，一旦当前丑数和2、3、5的乘积超过已知的最大丑数max，就分别记为m2=2*x; m3=3*y; m5=5*z，其中x、y、z为已知丑数中的某个丑数。m2,m3,m5中最小的那个记为下一个丑数。 //4. 这种记录中间值的方法，需要一个辅助数组，负责记录已出现过的丑数。返回第N个丑数。
public class Solution { public int GetUglyNumber_Solution(int index) { if(index<=0){ return 0; } int max = 0; int[] uglyes = new int[index]; uglyes[0] = 1; for(int i=1; i<index; i++){ uglyes[i] = getUgly(uglyes, uglyes[max]); max++; } return uglyes[max]; } //求下一个丑数 public int getUgly(int[] uglyes, int max){ //max传入的是当前已知的最大的丑数 int m2=0, m3=0, m5=0; for(int u:uglyes){ if(u*2>max){ m2=u*2; break; } } for(int u:uglyes){ if(u*3>max){ m3=u*3; break; } } for(int u:uglyes){ if(u*5>max){ m5=u*5; break; } } int temp = m2<m3 ? m2:m3; return temp<m5? temp:m5; } }