题目描述：LeetCode-面试题 17.09. 第 k 个数

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

示例 1:

输入: k = 5

输出: 9

解题思路一：三指针，想必大家都想到第k个数的排序是从1,3,5,7中选择它们相互乘积最小的第k个数。但是怎么编写代码思路呢？一：申请一个数组类似于动态规划记录前面的结果。二：res[i]=min(res[p3]*3,res[p5]*5,res[p7]*7)。其中p3,p5,p7分别记录之前的结果。三：如果取了一个数那么应该继续向前遍历，即选择一个p3,p5,p7进行++操作。

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

时间复杂度：O(k)
空间复杂度：O(k)

解题思路二：最小堆，每次取堆顶最小元素，与3,5,7进行相乘，seen记录是否已经取过。如此循环取出堆顶元素，第k次即是我们要的结果。

class Solution {
public:
    int getKthMagicNumber(int k) {
        vector<int> factors = {3, 5, 7};
        unordered_set<long> seen;
        priority_queue<long, vector<long>, greater<long>> heap;
        seen.insert(1L);
        heap.push(1L);
        int magic = 0;
        for (int i = 0; i < k; i++) {
            long curr = heap.top();
            heap.pop();
            magic = (int)curr;
            for (int factor : factors) {
                long next = curr * factor;
                if (!seen.count(next)) {
                    seen.insert(next);
                    heap.push(next);
                }
            }
        }
        return magic;
    }
};

时间复杂度：O(klogk)，k次循环，向堆中加入元素和取出元素都需要进行调整的时间复杂度为O(logk)。
空间复杂度：O(k)

解题思路三：暂无