设计一个算法。找出仅仅含素因子3
,5
,7
的第 k 大的数。
符合条件的数如:3。5。7,9,15......
您在真实的面试中是否遇到过这个题?
Yes
例子
假设k=4
, 返回 9
挑战
要求时间复杂度为O(nlogn)或者O(n)
分析:分别设三个指针,表明乘以3。5,7会大于当前丑数的index
代码:
class Solution {
public:
/*
* @param k: The number k.
* @return: The kth prime number as description.
*/
long long kthPrimeNumber(int k) {
// write your code here
vector<long long> v;
v.push_back(1LL);
int i = 0;
int j = 0;
int p = 0;
int cnt = 0;
while(cnt<k)
{
long long cur = min(min(v[i]*3,v[j]*5),v[p]*7);
v.push_back(cur);
while(v[i]*3<=cur)i++;
while(v[j]*5<=cur)j++;
while(v[p]*7<=cur)p++;
cnt++;
}
return v.back(); }
};