32 丑数

题目描述

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

代码一

分析
判断丑数:
首先除2，直到不能整除为止，然后除5到不能整除为止，然后除3直到不能整除为止。最终判断剩余的数字是否为1，如果是1则为丑数，否则不是丑数。

找丑数:

丑数能够分解成2^x_3^y_5^z,
所以只需要把得到的丑数不断地乘以2、3、5之后并放入他们应该放置的位置即可

public class Solution {
    public static void main(String[] args)
    {
        System.out.println(GetUglyNumber_Solution(0));
    }
    public static int GetUglyNumber_Solution(int index) {
        if(index<7)return index;
        int i=0,j=0,k=0;
        int[] arr = new int[index];
        arr[0] = 1;
        for(int m=1;m<index;m++)
        {
            arr[m] = Math.min(arr[i]*2, Math.min(arr[j]*3, arr[k]*5));
            //防止重复
            if(arr[i]*2==arr[m])i++;
            if(arr[j]*3==arr[m])j++;
            if(arr[k]*5==arr[m])k++;
        }
        return arr[index-1];
    }
}