求第1500个只有2,3,5因子的数.数是从小到大排列,第一个数是1,1=2^0*3^0*5^0.

求第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;
}