把只包含因子2，3和5的數(shù)稱作丑數(shù)（ugly number）。例如6，8都是丑數(shù)，但14不是，因?yàn)樗艘蜃?。習(xí)慣上我們把1作為第一個(gè)丑數(shù)。求按從小到大的順序的第N個(gè)丑數(shù)。

int GetUglyNumber_Solution(int index) {

? ? if (index<0) return 0;

? ? ? ? if (index==1) return 1;

? ? ? ? vector<int>k(index);

? ? ? ? k[0]=1;

? ? ? ? int num2=0,num3=0,num5=0;

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

? ? ? ? ? ? {

? ? ? ? ? ? k[i]=min(k[num2]*2,min(k[num3]*3,k[num5]*5));

? ? ? ? ? ? if(k[i]==k[num2]*2) num2++;

? ? ? ? ? ? if(k[i]==k[num3]*3) num3++;

? ? ? ? ? ? if(k[i]==k[num5]*5) num5++;

? ? ? ? }

? ? ? ? return k[index-1];

? ? }

注解:建立一個(gè)大小為N的數(shù)組或容器，前十個(gè)丑數(shù)是1，2，3，4，5，6，8，9，10，12。先從1的2倍，3倍，5倍中選一個(gè)最小數(shù)，作為第二個(gè)丑數(shù)，然后從1的3倍，5倍，2的2倍中選擇最小的數(shù)作為第三個(gè)丑數(shù)，然后從1的5倍，2的2倍，3的2倍中選一個(gè)最小的數(shù)作為下一個(gè)丑數(shù)......

每一個(gè)丑數(shù)都可以分解成一個(gè)或多個(gè)丑數(shù)的乘積。也可以看做之前已經(jīng)存好的丑數(shù)的2倍或3倍或5倍的數(shù)。怎么選取前面哪一個(gè)數(shù)的2倍，哪一個(gè)數(shù)的3倍，哪一個(gè)數(shù)的5倍是關(guān)鍵。

從最小的丑數(shù)開始，記錄他的2倍，3倍，5倍都是要取的，而且只能取一次，當(dāng)某個(gè)丑數(shù)的2倍取過之后，就更新改丑數(shù)，更新為下一個(gè)比它大的丑數(shù)；當(dāng)某個(gè)丑數(shù)的3倍取過之后，就更新丑數(shù)為下一個(gè)比他大的丑數(shù)；當(dāng)某個(gè)丑數(shù)的5倍取過之后，就更新丑數(shù)為下一個(gè)比它大的丑數(shù)。更新之后，記錄的仍為丑數(shù)的相對應(yīng)的倍數(shù)。依次更新數(shù)組或容器，最后返回第N和元素即可。