class Solution {
public:
int getKthMagicNumber(int k) {
}
};
面试题 17.09. 第 k 个数
有些数的素因子只有 3，5，7，请设计一个算法找出第 k 个数。注意，不是必须有这些素因子，而是必须不包含其他的素因子。例如，前几个数按顺序应该是 1，3，5，7，9，15，21。
示例 1:
输入: k = 5 输出: 9
原站题解
python3 解法, 执行用时: 40 ms, 内存消耗: 14.8 MB, 提交时间: 2022-08-26 14:54:39
class Solution:
def getKthMagicNumber(self, k: int) -> int:
dp = [0] * (k + 1)
dp[1] = 1
p3 = p5 = p7 = 1
for i in range(2, k + 1):
num3, num5, num7 = dp[p3] * 3, dp[p5] * 5, dp[p7] * 7
dp[i] = min(num3, num5, num7)
if dp[i] == num3:
p3 += 1
if dp[i] == num5:
p5 += 1
if dp[i] == num7:
p7 += 1
return dp[k]
python3 解法, 执行用时: 60 ms, 内存消耗: 14.9 MB, 提交时间: 2022-08-26 14:53:56
class Solution:
def getKthMagicNumber(self, k: int) -> int:
# 最小堆
factors = [3, 5, 7]
seen = {1}
heap = [1]
for i in range(k - 1):
curr = heapq.heappop(heap)
for factor in factors:
if (nxt := curr * factor) not in seen:
seen.add(nxt)
heapq.heappush(heap, nxt)
return heapq.heappop(heap)