跳转至

面试题 17.09. 第 k 个数#

问题描述#

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

示例 1:

输入: k = 5

输出: 9

解题思路#

用 \(s\) 保存得到的数，用指针 \(i_3,i_5,i_7\) 分别记录 \(3,5,7\) 所到达的位置，然后取出其中得到的最小值 \(\texttt{minn}=\min(s[i_3]\times3,s[i_5]\times5,s[i_7]\times7)\)。

  • \(\texttt{if minn}=s[i_3]\times3,i_3=i_3+1\).
  • \(\texttt{if minn}=s[i_5]\times5,i_5=i_5+1\).
  • \(\texttt{if minn}=s[i_7]\times7,i_7=i_7+1\).

ie

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def getKthMagicNumber(self, k: int) -> int:
        s = [0] * k
        s[0] = 1
        i3 = i5 = i7 = 0
        for i in range(1, k):
            a3, a5, a7 = s[i3] * 3, s[i5] * 5, s[i7] * 7
            minn = min(a3, a5, a7)
            s[i] = minn

            if minn == a3:
                i3 += 1
            if minn == a5:
                i5 += 1
            if minn == a7:
                i7 += 1
        return s[-1]
返回顶部

在手机上阅读