有些数的素因子只有 3，5，7，请设计一个算法找出第 k 个数。注意，不是必须有这些素因子，而是必须不包含其他的素因子。例如，前几个数按顺序应该是 1，3，5，7，9，15，21。

力扣

前情提要

小顶堆

维护一个堆，使该堆中的元素，最顶的元素值最小，每次插入新元素都要进行检查和重新传递

也可以直接使用优先队列，简单实用

三指针

同时维护三个数组，每个数组通过指针访问，然后比较后取出一个值+1

设计思路

因为最终数列中的每个值要么是3的倍数，要么是5的倍数，要么是7的倍数，我们完全可以暴力计算出来3，5，7倍数的值，然后从小到大一次排列后去重，当然，我们也完全可以不这么做，而是用一些更加优雅的解法，也就是上述的两个思路

代码实例

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    const vector<int> factors = {3, 5, 7};

    int getKthMagicNumber(int k) {
        priority_queue<long, vector<long>, greater<long>> q;
        unordered_set<long> vis;
        q.push(1l);
        vis.insert(1l);
        for (int i = 0; i < k - 1; ++i) {
            long cur = q.top();
            q.pop();
            for (int f : factors) {
                long nxt = cur * f;
                if (!vis.count(nxt)) {
                    vis.insert(nxt);
                    q.push(nxt);
                }
            }
        }
        return (int) q.top();
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public int getKthMagicNumber(int k) {
        int[] numList=new int[k+1];
        int p3=0,p5=0,p7=0;
        numList[0]=1;
        for(int i=1;i<k;i++){
            numList[i]=Math.min(Math.min(numList[p3]*3,numList[p5]*5),numList[p7]*7);
            if(numList[i]==numList[p3]*3) p3++;
            if(numList[i]==numList[p5]*5) p5++;
            if(numList[i]==numList[p7]*7) p7++;
        }
        return numList[k-1];
    }
}