lintcode 丑数

设计一个算法，找出只含素因子2，3，5 的第 n 大的数。
直接寻找丑数，由定义可知，丑数是由2^m，3n，5^l，因此不断寻找，将它们按从小到大的顺序排列，第n个即为结果。
首先定义一个vector（数组）存放结果，使数组的第一个数ugly[0]为1，然后从ugly[0]乘以2,ugly[0]乘以3,ugly[0]乘以5中选择最小的数为新的丑数，显然ugly[1]=2。然后再从ugly[1]乘以2,ugly[0]乘以3,ugly[0]乘以5中选择最小的数为下一个丑数，即ugly[2]=3。然后再从ugly[1]乘以2,ugly[1]乘以3，ugly[0]乘以5中选择最小的数，即ugly[3]=4。以此类推，得到最终结果。

class Solution {
public:
    /*
     * @param n an integer
     * @return the nth prime number as description.
     */
    int nthUglyNumber(int n) {
        // write your code here
        vector<int> ugly(n);
        int t2 = 0,t3 = 0, t5 = 0;
        ugly[0] = 1;
        for (int i = 1;i < n;i++) {
            ugly[i] = min(ugly[t2] * 2,min(ugly[t3] * 3,ugly[t5] * 5));
            if(ugly[i] == ugly[t2] * 2) t2++; 
            if(ugly[i] == ugly[t3] * 3) t3++;
            if(ugly[i] == ugly[t5] * 5) t5++;
        }
        return ugly.back();
    }    
};