LintCode 丑数 II

设计一个算法，找出只含素因子2，3，5 的第 n 小的数。

符合条件的数如：1, 2, 3, 4, 5, 6, 8, 9, 10, 12…

我们可以认为1也是一个丑数

样例：如果n = 9， 返回 10

挑战：要求时间复杂度为O(nlogn)或者O(n)

方法一：如果采用遍历的方式，无法完全通过，会造成超时。

class Solution {
public:
    /**
     * @param n: An integer
     * @return: the nth prime number as description.
     */
    long long nthUglyNumber(int n) {
        // write your code here
        int count = 0;  
        int i = 0;    
        while(count < n)  
        {  
            m++;  
            int number = i;  
            while(number % 2 == 0)  
                number = number / 2;  
            while(number % 3 == 0)  
                number = number / 3;  
            while(number % 5 == 0)  
                number = number / 5;  
            if(number == 1)  
            {  
                count++;  
            }  
        }  
        return i;  
    }
};

方法二：是从1开始构造丑数，然后依次计数。

class Solution {
public:
    /*
     * @param n an integer
     * @return the nth prime number as description.
     */
    int nthUglyNumber(int n) {
        // write your code here
        int count = 1;//统计丑数
        vector<int> ugly(n,0);//保存丑数
        ugly[0] = 1;//第一个丑数
        vector<int> idx(3,0);
        while(count < n)
        {
            int a = 2 * ugly[idx[0]];
            int b = 3 * ugly[idx[1]];
            int c = 5 * ugly[idx[2]];

            int temp = min(min(a, b), c);
            if(temp == a)
              ++idx[0];
            if(temp == b)
              ++idx[1];
            if(temp == c)
              ++idx[2];
            ugly[count] = temp;
            ++count;
        }
        return ugly[n-1];
    }
};