面试题 17.09.第 k 个数

【LetMeFly】面试题 17.09.第 k 个数

力扣题目链接：https://leetcode.cn/problems/get-kth-magic-number-lcci/

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

示例 1:

输入: k = 5

输出: 9

方法一：取最小

这道题和LeetCode 264. 丑数 II 几乎相同

具体方法可参考我在LeetCode 264. 丑数 II写的题解：https://blog.letmefly.xyz/2022/09/13/LeetCode 0264.丑数II

方法完全相同，用三个指针每次确定出一个最小值，哪个小就将哪个“入队”（加入候选）

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

AC代码

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int getKthMagicNumber(int k) {
        int loc3 = 0, loc5 = 0, loc7 = 0;
        vector<int> v = {1};
        while (--k) {
            int result3 = v[loc3] * 3;
            int result5 = v[loc5] * 5;
            int result7 = v[loc7] * 7;
            int m = min(result3, min(result5, result7));
            v.push_back(m);
            if (result3 == m) {
                loc3++;
            }
            if (result5 == m) {
                loc5++;
            }
            if (result7 == m) {
                loc7++;
            }
        }
        return v.back();
    }
};

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/127087237