题目描述
给定两个正整数 n
和 k
。
如果正整数 i
满足 n % i == 0
,那么我们就说正整数 i
是整数 n
的因子。
考虑整数 n
的所有因子,将它们 升序排列。请你返回第 k
个因子。如果 n
的因子数少于 k
,请你返回 -1
。
样例
输入:n = 12, k = 3
输出:3
解释:因子列表包括 [1, 2, 3, 4, 6, 12],第 3 个因子是 3。
输入:n = 7, k = 2
输出:7
解释:因子列表包括 [1, 7] ,第 2 个因子是 7。
输入:n = 4, k = 4
输出:-1
解释:因子列表包括 [1, 2, 4] ,只有 3 个因子,所以我们应该返回 -1。
输入:n = 1, k = 1
输出:1
解释:因子列表包括 [1] ,第 1 个因子为 1。
输入:n = 1000, k = 3
输出:4
解释:因子列表包括 [1, 2, 4, 5, 8, 10, 20, 25, 40, 50, 100, 125, 200, 250, 500, 1000]。
限制
1 <= k <= n <= 1000
算法1
(暴力枚举,数学) $O(\sqrt{n})$
- 暴力枚举因数,根据因数的性质,只需要枚举前 $\sqrt{n}$ 个数字。
时间复杂度
- 枚举前 $\sqrt{n}$ 个数字找到所有因数,故时间复杂度为 $O(\sqrt{n})$。
空间复杂度
- 需要额外 $O(\sqrt{n})$ 的空间记录所有的因数。
C++ 代码
class Solution {
public:
int kthFactor(int n, int k) {
vector<int> f1, f2;
for (int i = 1; i * i <= n; i++)
if (n % i == 0) {
f1.push_back(i);
if (i * i != n)
f2.push_back(n / i);
}
if (k <= f1.size())
return f1[k - 1];
if (k <= f1.size() + f2.size())
return f2[f2.size() + f1.size() - k];
return -1;
}
};