题目描述

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

思路

当前丑数乘以2或3或5就能得到下一个丑数。所以每得到一个丑数，下一次可以得到3个丑数
本题要求从小到大顺序的第index个丑数，所以每次要找到可以找到的最小丑数

第一个是1，接下来可以是1 * 2 , 1 * 3 , 1 * 5，此时最小的显然是2
接下来可以是2 * 2 , 2 * 3 , 2 * 5，此时就要把这次得到的三个4,6,10和上一次剩下的两个3,5比较大小，找出最小的，即3
接下来可以是3 * 2 , 3 * 3 , 3 * 5，…依次类推

法1：
本题可以建一个list，每次都对通过乘以某个丑数得到的三个数进行比较，找出其中最小的那个，放进list中
然后只把乘出这个数的那个上一趟丑数+1，继续向前寻找可能的丑数
最后找到n个丑数放进list里，最终返回list的最后一个元素值即可

法2：动态规划
和上面思路类似，写成动态规划的形式

实现

法1：

import java.util.ArrayList;
public class Solution {public int GetUglyNumber_Solution(int index) {/*当前丑数*2或*3或*5就能得到下一个丑数。每得到一个丑数，下一次可以得到3个丑数本题要求从小到大顺序的第index个丑数，所以每次要找到可以找到的最小丑数第一个是1，接下来可以是1*2,1*3,1*5，此时最小的显然是2接下来可以是2*2,2*3,2*5，此时就要把这次得到的三个和上一次剩下的两个比较大小，找出最小的*///思路：把每次都找出三个丑数中最小的，乘出这个最小数的上一个丑数就+1，继续向后找if(index==0) return 0;ArrayList<Integer> list=new ArrayList<>();  //存放找到的丑数list.add(1);   //第一个丑数是1//定义已经找到的用来乘以2,3,5的丑数在list中的下标int i2=0,i3=0,i5=0;//开始寻找丑数，加入到list中，只要List长度<index就一直找，list最后一个就是第Index个丑数while(list.size()<index){   //list长度不能等于index，会导致多循环一次//算出已找到的丑数*相应数之后得到的新丑数的值int m2=list.get(i2)*2;int m3=list.get(i3)*3;int m5=list.get(i5)*5;//求出此时三个数中最小的(比较三个数，库函数min要使用两次)int min=Math.min(m2,Math.min(m3,m5));//把当前得到的最小的丑数加入listlist.add(min);//哪个最小，就把乘出该数的丑数下标+1，使其继续向前乘出新丑数if(min==m2) i2++;if(min==m3) i3++;if(min==m5) i5++;}//返回list最后一个元素的值（即第index个丑数）return list.get(list.size()-1);}
}

法2：

public class Solution {public int GetUglyNumber_Solution(int index) {//思路相似，写成动态规划if(index==0) return 0;if(index==1) return 1;//dp[i]表示第i+1个丑数int[] dp=new int[index];dp[0]=1;   //第一个丑数是1//定义已经找到的用来乘以2/3/5的丑数在dp数组中的下标int i2=0,i3=0,i5=0;for(int i=1;i<index;i++){dp[i]=Math.min(dp[i2]*2,Math.min(dp[i3]*3,dp[i5]*5));    //当前最小的丑数加入数组中if(dp[i]==dp[i2]*2) i2++;if(dp[i]==dp[i3]*3) i3++;if(dp[i]==dp[i5]*5) i5++;}return dp[index-1];}
}