求第1500个只有2,3,5因子的数.数是从小到大排列,第一个数是1,1=2^0*3^0*5^0.
来源:学生作业帮 编辑:神马作文网作业帮 分类:综合作业 时间:2024/09/20 08:43:17
求第1500个只有2,3,5因子的数.数是从小到大排列,第一个数是1,1=2^0*3^0*5^0.
你的解释看了,最后还是不懂呢 “时间复杂度Nlog(N)” ,有没有其他的思路了?
你的解释看了,最后还是不懂呢 “时间复杂度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;
}
每次挑最小的乘以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;
}
求第1500个只有2,3,5因子的数.数是从小到大排列,第一个数是1,1=2^0*3^0*5^0.
求第1500个只有2,3,5因子的数.数是从小到大排列,第一个数是1,1=2^0*3^0*5^0
求第1500个只有2,3,5因子的数.数是从小到大排列,第一个数是1,1=2^0*3^0*5^0.只求编程的思路.
C编程:求第1500个只有2,3,5因子的数.数是从小到大排列,第一个数是1,1=2^0*3^0*5^0如题
0,1,2,3,这四个数组成非零自然数,从小到大排列,第103个数是几?
用0,1,2,3,4,五个数字组成不重复的五位数中,从小到大排列的第86个数是哪个数?
有一列从小到大排列的数,其最小的数是-3,之后每一个数都比前一个数大2,最大的一个数是155.记第n个数是y,求y关于n
一串数按1,1,2,2,3,3,4,4,5,5排列,从左边第一个数起,第83个数字是()
用1,2,3,4,6这五个数字组成能被11整除的五位数,将这些数从小到大排列,第6个数是
用 0,1,2,3,4,5这六个数组成的六位数,按从小到大排列,第二个偶数是
4个从小到大排列的连续偶数中,第2个数是2n-2,求这四个数的和?
一道数学规律探索题有一串神秘排列的数,从小到大的顺序排列为:1,1,2,3,5,8请问这列数的第8个数是______.