剑指Offer--【丑数】--java

题目描述：

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

解题思路：

选定第一个丑数1，根据丑数的定义，可知以后的丑数必然是在1的基础上乘以2，乘以3，乘以5，因此可以得出三个丑数，从中选择最小的一个添加到数组中，之后若数组中的丑数与得出的三个丑数中的一个或两个相等，将对应的下标后移，

代码如下：

public class Solution {
    public int GetUglyNumber_Solution(int index) {
        if(index<=0){
            return 0;
        }
        
        int[] result=new int[index];
        int m2=0;
        int m3=0;
        int m5=0;
        result[0]=1;
        for(int i=1;i<index;i++){
           int min=min(result[m2]*2,result[m3]*3,result[m5]*5);
            result[i]=min;
            if(result[m2]*2<=min){
                m2++;
            }
            if(result[m3]*3<=min){
                m3++;
            }
            if(result[m5]*5<=min){
                m5++;
            }
        }
        return result[index-1];
    }
    
    public static int min(int a,int b,int c){
       int min=(a<b?a:b);
       return (min<c?min:c);
    }
}

运行结果：