【2022-09-28每日一题】面试题 17.09. 第 k 个数[Medium]
2022-09-28
2分钟阅读时长
2022-09-28每日一题：面试题 17.09. 第 k 个数
难度：Medium
标签：哈希表 、 数学 、 动态规划 、 堆（优先队列）
有些数的素因子只有 3，5，7，请设计一个算法找出第 k 个数。注意，不是必须有这些素因子，而是必须不包含其他的素因子。例如，前几个数按顺序应该是 1，3，5，7，9，15，21。
示例 1:
输入: k = 5 输出: 9
方法一：堆（优先队列）
// 小顶堆
type hp struct { sort.IntSlice }
func (h hp) Less(i, j int) bool { return h.IntSlice[i] < h.IntSlice[j] }
func (h *hp) Push(v interface{}) {h.IntSlice = append(h.IntSlice, v.(int))}
func (h *hp) Pop() (v interface{}) { v, h.IntSlice = h.IntSlice[h.Len()-1], h.IntSlice[:h.Len()-1]; return v}
var factors = []int{3, 5, 7}
func getKthMagicNumber(k int) int {
h := hp{sort.IntSlice{1}}
mp := map[int]struct{}{1: {}}
for i := 1; ;i++ {
v := heap.Pop(&h).(int)
if i == k {
return v
}
for _, n := range factors {
n *= v
if _, ok := mp[n]; !ok { // 判重
mp[n] = struct{}{}
heap.Push(&h, n)
}
}
}
}
复杂度分析
- 时间复杂度：O(klogk)
- 空间复杂度：O(k)
方法二：动态规划
详细思路过程见官方题解，这里只做个人刷题记录，方便后续查询阅读
func getKthMagicNumber(k int) int {
dp := make([]int, k + 1)
dp[1] = 1
p3, p5, p7 := 1, 1, 1
for i := 2; i <= k; i++ {
v1, v2, v3 := dp[p3]*3, dp[p5]*5, dp[p7]*7
dp[i] = min(v1, min(v2, v3))
if dp[i] == v1 {
p3++
}
if dp[i] == v2 {
p5++
}
if dp[i] == v3 {
p7++
}
}
return dp[k]
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
复杂度分析
- 时间复杂度：O(k)
- 空间复杂度：O(k)