Ugly Number

Ugly number is a number that only have factors 3, 5 and 7.

Design an algorithm to find the Kth ugly number. The first 5 ugly numbers are 3, 5, 7, 9, 15 ...

http://www.lintcode.com/en/problem/ugly-number/

Discussion

维护一个最小堆，每一个push的值都是3, 5, 7的倍数，返回第K个弹出的值。

Solution

long long kthPrimeNumber(int k) {
        //maintain a min-heap, output k times
        //the input od the heap depends on the top element
        priority_queue<long long, vector<long long>, greater<long long> > minheap;
        //init heap
        minheap.emplace(3);
        minheap.emplace(5);
        minheap.emplace(7);
        //out put k times
        long long ugly_num = 0;
        for(int i=0; i<k; i++) {
            ugly_num = minheap.top();
            minheap.pop();
            if(ugly_num % 3 ==0) {
                minheap.emplace(ugly_num*3);
            } else if(ugly_num % 5 ==0) {
                minheap.emplace(ugly_num*3);
                minheap.emplace(ugly_num*5);
            } else {
                minheap.emplace(ugly_num*3);
                minheap.emplace(ugly_num*5);
                minheap.emplace(ugly_num*7);
            }
        }
        return ugly_num;
    }

Follow up

O(KlogK) rum time.
O(k) space.

也可以用BST实现，BST对应数组是升序的，所以第1个元素总是最小的。总体时间复杂度和用heap是一样的，只是emplace是logN复杂度，erase一个position是O(1).

long long kthPrimeNumber(int k) {
        //using a BST
        set<long long> myset;
        //init BST
        myset.emplace(3);
        myset.emplace(5);
        myset.emplace(7);
        //the input of BST are ungly numbers
        //the first elemeent of BST is the smallest one
        //so we erase the first element K times
        long long ugly_num = 0;
        for(int i=0; i<k; i++) {
            ugly_num = *myset.begin();
            myset.erase(myset.begin());//delete the smallest one
            if(ugly_num % 3 == 0) {
                myset.emplace(ugly_num*3);
            } else if(ugly_num % 5 == 0) {
                myset.emplace(ugly_num*3);
                myset.emplace(ugly_num*5);
            } else {
                myset.emplace(ugly_num*3);
                myset.emplace(ugly_num*5);
                myset.emplace(ugly_num*7);
            }
        }
        return ugly_num;
    }

还有个动归的解法，不懂。。

class Solution {
public:
    /*
     * @param k: The number k.
     * @return: The kth prime number as description.
     */
    long long kthPrimeNumber(int k) {
        vector<long long> uglies(k + 1);
        uglies[0] = 1;

        long long f3 = 3, f5 = 5, f7 = 7;
        int idx3 = 0, idx5 = 0, idx7 = 0;

        for (int i = 1; i <= k; ++i) {
            long long min_val = min(min(f3, f5), f7);
            uglies[i] = min_val;

            if (min_val == f3) {
                f3 = 3 * uglies[++idx3];
            }
            if (min_val == f5) {
                f5 = 5 * uglies[++idx5];
            }
            if (min_val == f7) {
                f7 = 7 * uglies[++idx7];
            }
        }

        return uglies[k];
    }
};