求第1500个只有2,3,5因子的数.数是从小到大排列,第一个数是1,1=2^0*3^0*5^0.你的解释看了,最后还是不懂呢 “时间复杂度Nlog(N)” ,有没有其他的思路了?
来源：学生作业帮助网 编辑：六六作业网 时间：2024/12/20 13:20:48
求第1500个只有2,3,5因子的数.数是从小到大排列,第一个数是1,1=2^0*3^0*5^0.你的解释看了,最后还是不懂呢 “时间复杂度Nlog(N)” ,有没有其他的思路了?
求第1500个只有2,3,5因子的数.数是从小到大排列,第一个数是1,1=2^0*3^0*5^0.
你的解释看了,最后还是不懂呢 “时间复杂度Nlog(N)” ,有没有其他的思路了?
求第1500个只有2,3,5因子的数.数是从小到大排列,第一个数是1,1=2^0*3^0*5^0.你的解释看了,最后还是不懂呢 “时间复杂度Nlog(N)” ,有没有其他的思路了?
第一个数是1,然后扩展出了{2,3,5}
每次挑最小的乘以2,3,5,扩展出三个数
每次选出最小的数,最小堆就能解决.
就是一个取堆顶,把扩展后的数放入堆中的过程.
每次插堆的复杂度是 log(N),一共有3*N个数,所以就是 N*log(N)
你看看堆是什么东西
一个小代码,你可以看看
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
class cmp{
public:
bool operator()(const long long& a,const long long& b) {
return a > b;
}
};
priority_queue<long long,vector<long long>,cmp> minHeap;
/*
上面的代码: priority_queue是一个优先队列,每次取最小的一个数.
C++ STL 自己实现的,可以看看什么是优先队列,什么是堆.
每次往优先队列插入一个数或者删除一个数的复杂度是 log(N)
*/
int main() {
int n;
while ( scanf("%d", &n) != EOF) { //找第n个满足要求的数
minHeap.push(1); //第一个数是 1
for (int i = 1; i < n; ++i) {
long long minValue = minHeap.top(); //得到当前最小的数
while (minHeap.top() == minValue) { //把重复的都删掉
minHeap.pop();
}
minHeap.push(minValue*2); //用最小的数乘以2,3,5进行扩展
minHeap.push(minValue*3);
minHeap.push(minValue*5);
}
long long ans = minHeap.top(); //第n次的最小的数就是答案了.因为1500可能超过int的最大数值了,所以用long long
printf("the %dth num is %lld\n", n, ans);
while (!minHeap.empty()) {
minHeap.pop();
}
}
return 0;
}