目錄
一，題目描述
英文描述
中文描述
二，解題思路
1，算法
2，算法有效性
2.1 不重複
2.2 不遺漏
三，AC代碼
C++
四，解題過程
第一博
一，題目描述
英文描述
Design an algorithm to find the kth number such that the only prime factors are 3, 5, and 7. Note that 3, 5, and 7 do not have to be factors, but it should not have any other prime factors. For example, the first several multiples would be (in order) 1, 3, 5, 7, 9, 15, 21.
Example 1:
Input: k = 5
Output: 9
中文描述
有些數的素因子隻有 3，5，7，請設計一個算法找出第 k 個數。注意，不是必須有這些素因子，而是必須不包含其他的素因子。例如，前幾個數按順序應該是 1，3，5，7，9，15，21。
示例 1:
輸入: k = 5
輸出: 9
來源：力扣（LeetCode）
連結：https://leetcode-cn.com/problems/get-kth-magic-number-lcci 著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。
二，解題思路
1，算法
利用一個數組從小到大記錄所有符合條件的值，當數組大小為k時，傳回數組中最後一個值即可。
以k=5為例。具體算法直接上圖：
1，初始化。3、5、7指針位置對應數組中的下标0.
2，将最小值3壓入數組，指針3對應位置後移一位，進行下一輪循環
3，将最小值5壓入數組，指針5對應位置後移一位，進行下一輪循環
4，将最小值7壓入數組，指針7對應位置後移一位，進行下一輪循環
5，将最小值9壓入數組，指針3對應位置後移一位，進行下一輪循環
6，将最小值15壓入數組，指針3、5對應位置後移一位，進行下一輪循環
7，數組大小等于5傳回15即可。
2，算法有效性
2.1 不重複
由于壓入數組的值永遠大于數組中最後一個值，是以所有元素均不重複。
2.2 不遺漏
壓入數組的每一個值都是由最小的元素組成的，可以保證沒有遺漏。
三，AC代碼
C++
class Solution {
public:
int getKthMagicNumber(int k) {
vector<int> record;
record.push_back(1);
int indexOf3 = 0, indexOf5 = 0, indexOf7 = 0;
while (record.size() < k) {
int valueOf3 = record[indexOf3] * 3;
int valueOf5 = record[indexOf5] * 5;
int valueOf7 = record[indexOf7] * 7;
int minValue = min(min(valueOf3, valueOf5), valueOf7);
record.push_back(minValue);
if (valueOf3 == minValue) indexOf3++;
if (valueOf5 == minValue) indexOf5++;
if (valueOf7 == minValue) indexOf7++;
}
return record[record.size() - 1];
}
};