***劍指offer-醜數

題目描述，輸入一個N，輸出第N個醜數。 醜數的意思是質因子是2，3，5的數，規定1是第一個醜數。

思路：既然質因子是2，3，5,  那麼一個醜數肯定就隻能是2^a*3^b*5^c 的數，a,b,c為指數，醜數乘醜數也依舊是醜數。隻要能正确的組合a,b,c，取不同的值，然後可以得到從小到達的醜數，那麼題目就容易做出來了。可是怎麼才能實作呢。

考慮兩個不等式，  對于p，2*p<3*p<5*p，  對于2，不同數p<q，則2*p<2*q。

一開始第一個醜數是1，這時候候選的醜數有 1*2 、1*3、1*5 ，找出他們中最小的，即2，并從候選醜數中剔除2。

此時第二個醜數是2了，這時候候選的醜數有1*3、1*5、2*2、2*3、2*5。若我們不通過上面兩個不等式将候選集縮小，則會導緻需要比較的數的個數變得非常多，那時間複雜度特别高。此時，觀察到1*3<2*3、1*5<2*5是以可以直接剔除後面這兩個數。

進而隻需要比較2*2 、1*3、1*5了。之後都可以按照這個規則。會發現通過底數或者指數來比較，每次都會剔除到3個數。

java程式：

public class Solution {

    public int GetUglyNumber_Solution(int index) {

        if(index<7)

            return index;

        int[] arr = new int[index];

        arr[0]=1;

        int t1=0,t2=0,t3=0;

        for(int i =1;i<index;i++){

            arr[i]=Math.min(2*arr[t1],Math.min(3*arr[t2],5*arr[t3]));

            if(arr[t1]*2==arr[i])t1++;

            if(arr[t2]*3==arr[i])t2++;

            if(arr[t3]*5==arr[i])t3++;

        }

        return arr[index-1];

    }

}