第 k 个数（LeetCode）

LeetCode原题链接

题目描述

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

示例 1:

输入: k = 5 输出: 9

思路

这道题显然和剑指offer的丑数一样套路，可以理解为维护了三个队列：乘以3的队列、乘以5的队列、乘以7的队列，具体实现时用三个指针来完成。

具体思路见丑数（剑指offer）。

代码如下：

class Solution { public: int getKthMagicNumber(int k) { int p3=0,p5=0,p7=0; vector<int> arr(1,1); while(arr.size()<k){ int minnum=min(arr[p3]*3,min(arr[p5]*5,arr[p7]*7)); if(arr[p3]*3==minnum) p3++; if(arr[p5]*5==minnum) p5++; if(arr[p7]*7==minnum) p7++; arr.push_back(minnum); } return arr[arr.size()-1]; } };