LintCode 丑数

中等 丑数 查看执行结果 

20%

通过

设计一个算法，找出仅仅含素因子3，5。7 的第 k 大的数。

符合条件的数如：3。5。7。9，15......

您在真实的面试中是否遇到过这个题？ 

Yes

例子

假设k=4， 返回 9

挑战

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

class Solution {
public:
    /*
     * @param k: The number k.
     * @return: The kth prime number as description.
     */
     template <class T> 
     T minnum (T a, T b, T c) {
         T temp  =  a > b ?
 b:a;
         return temp < c ?
 temp :c;
     }
    long long kthPrimeNumber(int k) {
        // write your code here
        long long *result = new long long[k];
        result [0] = 3;
        result [1] = 5;
        result [2] = 7;
        int a3 = 0;
        int a5 = 0;
        int a7 =0;
        for (int i = 3; i < k; ++i) {
            result[i] = minnum(result[a3] * 3, result[a5] * 5, result[a7] * 7);
            while (result[a3] * 3 <= result[i]) {
                ++a3;
            }
            while (result[a5] * 5 <= result[i]) {
                ++a5;
            }
            while (result[a7] * 7 <= result[i]) {
                ++a7;
            }
        }
        return result[k-1];
    }
};