LintCode-丑数

设计一个算法。找出仅仅含素因子357 的第 k 大的数。

符合条件的数如:3。5。7,9,15......

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

Yes
例子

假设k=4, 返回 9

挑战

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

标签 Expand



相关题目 Expand

分析:分别设三个指针,表明乘以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(); }
};
上一篇:应用的启动视图 LauchView


下一篇:dubbo 分布式架构学习视频链接