LintCode-丑数
2024-10-14 17:32:12
设计一个算法。找出仅仅含素因子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(); }
};
最新文章
- iOS实现UITableViewDataSource与Controller的分离
- iOS Error
- ubuntu apt-get update 失败解决
- haohantechsoft-PDA软件,PDA管理软件,PDA管理系统,仓库PDA销售开单盘点软件
- opscenter dashboard排错
- Epplus 使用的简单介绍
- ThinkPHP 的CURD 基本操作
- HDU 2553 N皇后问题(dfs)
- SIMPASS技术解析
- Mysql锁机制--乐观锁 &; 悲观锁
- 搭建docker私有仓库(https)
- 常见程序入口点(OEP)特征
- 使用Request+正则抓取猫眼电影(常见问题)
- Solidity(address的四个方法)
- 当我们直接打印定义的对象的时候,隐含的是打印toString()的返回值。
- Unity3D笔记 英保通三 脚本编写 、物体间通信
- NOI 4978 宠物小精灵之收服(二维背包)
- 7-nginx-keepalived配置主从双击热备
- 监控操作系统的CPU、内存、磁盘
- 2.2 vivi虚拟视频驱动测试