中等

问题描述

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

示例 1:

输入: k = 5

输出: 9

动态规划

/**
 * @param {number} k
 * @return {number}
 */
var getKthMagicNumber = function (k) {
  const dp = new Array(k + 1)
  dp[1] = 1
  let i3 = 1
  let i5 = 1
  let i7 = 1
  for (let i = 2; i <= k; i++) {
    const a = dp[i3] * 3
    const b = dp[i5] * 5
    const c = dp[i7] * 7
    const next = Math.min(a, b, c)
    if (a === next) i3++
    if (b === next) i5++
    if (c === next) i7++
    dp[i] = next
  }
  return dp[k]
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$