LeetCode 面试题 17.09. 第 k 个数

Question

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

示例 1:

输入: k = 5
输出: 9

---

前置知识

• 堆
• 状态机
• 动态规划

堆

思路

思路很简单。 就是使用一个小顶堆，然后每次从小顶堆取一个， 取 k 次即可。

唯一需要注意的是重复数字，比如 3 * 5 = 15 ， 5 * 3 = 15 。关于去重， 用 set 就对了。

关键点

• 去重

代码(Python)

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

状态机

思路

思路很简单， 就是用三个指针记录因子是 3，5，7 的最小值的索引。

代码（Python）

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)$