1:
题目描述
把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
int GetUglyNumber_Solution(int index) {if(index==1)return 1;if(index<=0)return 0;//考虑N=2^X*3^Y*5^z 只需要比较每次最小的即可int p2=0,p3=0,p5=0;vector<int> result(index,0);result[0]=1;for(int i=1;i<index;++i){result[i]=min(result[p2]*2,min(result[p3]*3,result[p5]*5));if(result[i]==result[p2]*2)p2++; //需要注意的是可能产生重复if(result[i]==result[p3]*3)p3++;if(result[i]==result[p5]*5)p5++;}return result[index-1];}
注意：之所以用3个if，是因为可能会出现2*3=3*2这种重复情况。3个if用来去除重复。