# 面试题 17.09. 第 k 个数
## 题目描述
```
有些数的素因子只有 3，5，7，请设计一个算法找出第 k 个数。注意，不是必须有这些素因子，而是必须不包含其他的素因子。例如，前几个数按顺序应该是 1，3，5，7，9，15，21。
示例 1:
输入: k = 5
输出: 9
```
## 前置知识
* 堆
* 状态机
* 动态规划
## 公司
* 暂无
## 堆
### 思路
思路很简单。 就是使用一个小顶堆，然后每次从小顶堆取一个， 取 k 次即可。
唯一需要注意的是重复数字，比如 `3 * 5 = 15` ， `5 * 3 = 15` 。关于去重， 用 set 就对了。
### 关键点
* 去重
### 代码(Python)
```py
from heapq import heappop, heappush
class Solution:
def getKthMagicNumber(self, k: int) -> int:
heap = [1]
numbers = set()
# 每次从小顶堆取一个， 取 k 次即可
while k:
cur = heappop(heap)
if cur not in numbers:
k -= 1
heappush(heap, cur * 3)
heappush(heap, cur * 5)
heappush(heap, cur * 7)
numbers.add(cur)
return cur
```
## 状态机
### 思路
这个思路力扣的题目还是蛮多的， 比如西法我之前写的一个 [《原来状态机也可以用来刷 LeetCode？》](https://lucifer.ren/blog/2020/01/12/1262.greatest-sum-divisible-by-three/).
思路很简单， 就是用三个指针记录因子是 3，5，7 的最小值的索引。
### 代码（Python）
```py
class Solution:
def getKthMagicNumber(self, k: int) -> int:
p3 = p5 = p7 = 0
state = [1] + [0] * (k - 1)
for i in range(1, k):
state[i] = min(state[p3] * 3, state[p5] * 5, state[p7] * 7)
if 3 * state[p3] == state[i]: p3 += 1
if 5 * state[p5] == state[i]: p5 += 1
if 7 * state[p7] == state[i]: p7 += 1
return state[-1]
```
**复杂度分析**
* 时间复杂度：$O(k)$
* 空间复杂度：$O(k)$
大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 36K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/get-kth-magic-number-lcci.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.