(牛客網)醜數

把隻包含因子2、3和5的數稱作醜數（Ugly Number）。例如6、8都是醜數，但14不是，因為它包含因子7。 習慣上我們把1當做是第一個醜數。求按從小到大的順序的第N個醜數。

要了解下面的算法需要注意：

1.每個醜數都是之前的醜數 *2 ， *3 ， *5 的結果

2.一個醜數 * x (x=2,3,5) 的結果都要加入到答案序列中，但是每次隻能加入最小的那個。一旦一個醜數 * x (x=2,3,5) 被加入到答案序列中，那麼目前醜數就要更新為答案序列中下一個醜數。

例如：目前答案序列 1

我們會得到 3 個待選醜數 2 3 5

我們選擇最小的2加入到答案序列中，更新答案序列為：1 2

此時 3 個待選醜數變為 4 3 5 (4=2*2)

我們選擇最小的3加入到答案序列中，更新答案序列為：1 2 3

此時 3 個待選醜數變為 4 6 5 (6=2*3)

我們選擇最小的4加入到答案序列中，更新答案序列為：1 2 3 4

此時 3 個待選醜數變為 6 6 5 (6=3*2)

我們選擇最小的5加入到答案序列中，更新答案序列為：1 2 3 4 5

此時 3 個待選醜數變為 6 6 10 (10=2*5)

….

這樣得到的答案序列一定為升序

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        if(index==)
            return ;
        int x2,x3,x5;
        x2=x3=x5=;
        int *ug=new int[index];
        ug[]=;
        for(int i=;i<index;i++){
            int t = min(ug[x2]*2,min(ug[x3]*3,ug[x5]*5));
            if(t==ug[x2]*2) x2++;
            if(t==ug[x3]*3) x3++;
            if(t==ug[x5]*5) x5++;
            ug[i]=t;
        }
        return ug[index-];
    }
};