Write a program to find the n-th ugly number.
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.
Note that 1 is typically treated as an ugly number.
思路
《剑指Offer》上的原题34，所以就说个大概吧。
下一个丑数是之前的丑数（最初是1）乘以2、3或者5得到的，所以下一个丑数就是之前的某个数乘出来的。这样的找法比从1到n一个个判断是不是丑数高效很多，不然每个数都要去除个2、3、5判断一下。
由于要管次序问题，所以安排三个指针，分别记录乘以2、3、5后不超过当前最大丑数的位置，假设是p2, p3, p5，下一次找下个丑数的时候，从(p2)2、(p3)3、(p5)5里头找到个最小的，加在数组最后面，然后更新三个指针的值，如此往复……
代码
class Solution {
public:
int nthUglyNumber(int n) {
if(n <= 0)
return 0;
int* uglyAry = new int[n];
uglyAry[0] = 1;
int nextPos = 1;
int *pNextUgly2 = uglyAry;
int *pNextUgly3 = uglyAry;
int *pNextUgly5 = uglyAry;
while(nextPos < n){
int nextUgly = min3(*pNextUgly2 * 2, *pNextUgly3 * 3, *pNextUgly5 * 5);
uglyAry[nextPos] = nextUgly;
//Move forward to find next possible candidates
while(*pNextUgly2 * 2 <= nextUgly)
pNextUgly2++;
while(*pNextUgly3 * 3 <= nextUgly)
pNextUgly3++;
while(*pNextUgly5 * 5 <= nextUgly)
pNextUgly5++;
nextPos++;
}
int ugly = uglyAry[n-1];
delete []uglyAry;
return ugly;
}
int min3(int n1, int n2, int n3){
int min = n1<n2?n1:n2;
min = min<n3?min:n3;
return min;
}
};