264 Ugly Number II

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.

Hint:

• The naive approach is to call isUgly for every number until you reach the nth one. Most numbers are not ugly. Try to focus your effort on generating only the ugly ones.
• An ugly number must be multiplied by either 2, 3, or 5 from a smaller ugly number.
• The key is how to maintain the order of the ugly numbers. Try a similar approach of merging from three sorted lists: L1, L2, and L3. Assume you have $$Uk$$, $$U{k+1}$$ must be Min($$L_1 2$$, $$L_2 3$$, $$L_3 * 5$$).

A very smart solution from online discussion

class Solution {
public:
    int nthUglyNumber(int n) {
        if ( n <= 0 ) return 0;
        if ( n == 1 ) return 1;
        vector<int> ugly(n, 1);
        int t2 = 0, t3 = 0, t5 = 0;
        for ( int i = 1; i <= n-1; i++ ) {
            ugly[i] = min(ugly[t2]*2, min(ugly[t3]*3, ugly[t5]*5));
            // the following step actually takes care of the duplicates e.g. 2*3 = 3*2 = 6 case
            if ( ugly[i] == ugly[t2]*2 ) t2 += 1;
            if ( ugly[i] == ugly[t3]*3 ) t3 += 1;
            if ( ugly[i] == ugly[t5]*5 ) t5 += 1;
            cout << ugly[i] << endl;
        }
        return ugly[n-1];
    }
};

my less smart solution using heap

class Solution {
public:
    int nthUglyNumber(int n) {
        priority_queue<long> heap;
        heap.push(-1);
        int icount = 0;
        long target, prev = 0;
        while ( true ) {
            while ( true ) {
                target = heap.top();
                heap.pop();
                if ( target != prev ) break;
            }
            prev = target;
            icount += 1;
            if ( icount == n ) break;
            heap.push(target*2);
            heap.push(target*3);
            heap.push(target*5);
        }
        return -target;
    }
};

这个解法的缺点在于，比较浪费memory。

• 重复的数存了好几遍（可以额外用set解决，但也要花额外的memory）
• 当我们得到最后一个target的时候，heap里存了许多在target后面的数（我们并不需要，但也没办法判断什么时候不要再push数进去了。。）。

313. super ugly number:

利用标记index的方法解决一道类似的题

class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        int p = primes.size();
        vector<int> index(p, 0);
        vector<int> res(1, 1);
        while ( res.size() < n ) {
            int next = INT_MAX;
            for ( int i = 0; i < p; i++ ) next = min(next, res[index[i]]*primes[i]);
            res.push_back(next);
            for ( int i = 0; i < p; i++ ) {
                if ( res[index[i]]*primes[i] == next ) index[i] += 1;
            }
        }
        return res[n-1];
    }
};