编写程序找第 n
个丑数。
丑数就是只包含质因子 2, 3, 5
的正整数。
例如, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12
就是前10个丑数。
注意:
1. 1
一般也被当做丑数
2. n
不超过1690
思路:丑数是能完全被2,3,5整除的,比如12=2*2*3; 27=3*3*3;但是14就不是丑数,因为14=2*7,含有其他因子7;所以所有的丑数都可以分解为2,3,5的乘积。因而我们可以通过前面的丑数来求得后面的丑数,通过前面的丑数乘以2,3,或者5就能得到后面的丑数;用三个地址num2,num3, num5来表示乘以2,3,5得到丑数的位置。比如已经有了第一个丑数1, 可以得到2,3,5,再通过这三个丑数可以得到4,6,10,9,15,25...依次这样下去就能得到所有的丑数。
有一个注意点是,新的丑数是从当前num2,num3,num5指向的最小的丑数得到的。eg,此时num2,num3,num5指向的丑数分别为2,1,1.那么下一个丑数应该是3.并且更新这三个的地址
1 class Solution { 2 public: 3 int minn(int a, int b, int c){ 4 return a>b?(b>c?c:b):(a>c?c:a); 5 } 6 int nthUglyNumber(int n) { 7 int i = 1, num2 = 0, num3 = 0, num5 = 0, val = 1; 8 int *ugly = new int[n]; 9 ugly[0] = 1; 10 while(i < n){ 11 val = minn(ugly[num2]*2, ugly[num3]*3, ugly[num5]*5); 12 if(ugly[num2]*2 == val) num2++; 13 if(ugly[num3]*3 == val) num3++; 14 if(ugly[num5]*5 == val) num5++; 15 ugly[i++] = val; 16 } 17 return ugly[n-1]; 18 } 19 };