第五章 - 高频考题(中等)
1906. 查询差绝对值的最小值
面试题 17.09. 第 k 个数

题目描述

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

前置知识

  • 状态机
  • 动态规划

公司

  • 暂无

思路

思路很简单。 就是使用一个小顶堆,然后每次从小顶堆取一个, 取 k 次即可。
唯一需要注意的是重复数字,比如 3 * 5 = 155 * 3 = 15 。关于去重, 用 set 就对了。

关键点

  • 去重

代码(Python)

1
from heapq import heappop, heappush
2
class Solution:
3
def getKthMagicNumber(self, k: int) -> int:
4
heap = [1]
5
numbers = set()
6
# 每次从小顶堆取一个, 取 k 次即可
7
while k:
8
cur = heappop(heap)
9
if cur not in numbers:
10
k -= 1
11
heappush(heap, cur * 3)
12
heappush(heap, cur * 5)
13
heappush(heap, cur * 7)
14
numbers.add(cur)
15
return cur
Copied!

状态机

思路

这个思路力扣的题目还是蛮多的, 比如西法我之前写的一个 《原来状态机也可以用来刷 LeetCode?》.
思路很简单, 就是用三个指针记录因子是 3,5,7 的最小值的索引。

代码(Python)

1
class Solution:
2
def getKthMagicNumber(self, k: int) -> int:
3
p3 = p5 = p7 = 0
4
state = [1] + [0] * (k - 1)
5
6
for i in range(1, k):
7
state[i] = min(state[p3] * 3, state[p5] * 5, state[p7] * 7)
8
if 3 * state[p3] == state[i]: p3 += 1
9
if 5 * state[p5] == state[i]: p5 += 1
10
if 7 * state[p7] == state[i]: p7 += 1
11
return state[-1]
Copied!
复杂度分析
  • 时间复杂度:$O(k)$
  • 空间复杂度:$O(k)$
大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 36K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。