基于队列寻找第K个数

题目解决思路代码说明

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

使用队列进行解决，初始化队列的第一个节点的值为1。使用3个指针p3、p5、p7计算下一个数，初始时刻，p3、p5、p7都指向队列的第一个节点。每一轮计算过程中，p3指向的节点的值乘以3，p5指向的节点的值乘以5，p7指向的节点的值乘以7。选择上述每一轮计算出的最小值压入队列，并将最小值对应的指针向后移动一位。注意：当在某一轮计算中，有多个指针对应计算出的值相等且都是最小值时，只向队列中压入一个值，但最小值对应的所有指针都要向后移动一位。上述过程如下图所示：
代码

C++代码

# include 
# include 
# include 

using namespace std;

class Solution {
public:
    int getKthMagicNumber(int k) {
        vector  arr;       // 使用数组实现队列
        arr.push_back(1);       // 初始化队列的头节点为1
        int p3 = 0;
        int p5 = 0;
        int p7 = 0;

        while (arr.size() < k) {
            int ret = arr[p3] * 3;
            ret = min(ret, arr[p5] * 5);
            ret = min(ret, arr[p7] * 7);
            if (ret == arr[p3] * 3) {
                p3++;
            } else if (ret == arr[p5] * 5) {
                p5++;
            } else if (ret == arr[p7] * 7) {
                p7++;
            }
            
            arr.push_back(ret);
        }
        return arr[k - 1];
    }
};


int main() {
    Solution *solution = new Solution();
    int k = 5;
    printf("%d", solution->getKthMagicNumber(k));
    return 0;
}

对应LeetCode第17.09题。链接：https://leetcode-cn.com/problems/get-kth-magic-number-lcci/