英文原文
Given two positive integers n and k.
A factor of an integer n is defined as an integer i where n % i == 0.
Consider a list of all factors of n sorted in ascending order, return the kth factor in this list or return -1 if n has less than k factors.
Example 1:
Input: n = 12, k = 3 Output: 3 Explanation: Factors list is [1, 2, 3, 4, 6, 12], the 3rd factor is 3.
Example 2:
Input: n = 7, k = 2 Output: 7 Explanation: Factors list is [1, 7], the 2nd factor is 7.
Example 3:
Input: n = 4, k = 4 Output: -1 Explanation: Factors list is [1, 2, 4], there is only 3 factors. We should return -1.
Example 4:
Input: n = 1, k = 1 Output: 1 Explanation: Factors list is [1], the 1st factor is 1.
Example 5:
Input: n = 1000, k = 3 Output: 4 Explanation: Factors list is [1, 2, 4, 5, 8, 10, 20, 25, 40, 50, 100, 125, 200, 250, 500, 1000].
Constraints:
1 <= k <= n <= 1000
中文题目
给你两个正整数 n 和 k 。
如果正整数 i 满足 n % i == 0 ，那么我们就说正整数 i 是整数 n 的因子。
考虑整数 n 的所有因子，将它们 升序排列 。请你返回第 k 个因子。如果 n 的因子数少于 k ，请你返回 -1 。
示例 1：
输入：n = 12, k = 3 输出：3 解释：因子列表包括 [1, 2, 3, 4, 6, 12]，第 3 个因子是 3 。
示例 2：
输入：n = 7, k = 2 输出：7 解释：因子列表包括 [1, 7] ，第 2 个因子是 7 。
示例 3：
输入：n = 4, k = 4 输出：-1 解释：因子列表包括 [1, 2, 4] ，只有 3 个因子，所以我们应该返回 -1 。
示例 4：
输入：n = 1, k = 1 输出：1 解释：因子列表包括 [1] ，第 1 个因子为 1 。
示例 5：
输入：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 到 n 的每一个数字，看是不是 n 的因子，就可以通过(C++)。
class Solution {
public:
int kthFactor(int n, int k) {
vector<int> factors;
for(int i = 1; i <= n; i ++)
if(n % i == 0) factors.push_back(i);
return k - 1 < factors.size() ? factors[k - 1] : -1;
}
};上述算法时间是 O(n) 的，空间是 O(n) 的。
很多同学都知道，求解一个数字的所有因子，使用 O(sqrt(n)) 的时间就可以。
这是因为，当我们知道 d 是 n 的因子的时候，就知道了 n / d 也是 n 的因子。所以，我们只需要从 1 搜索到 sqrt(n) 就足够了。
但是因为这个问题最后要将所有因子按照升序排列，因此，以下代码虽然在 O(sqrt(n)) 的时间里完成了查找 n 的所有因子，但最终排序反而让复杂度升高了。
不过通过以下代码，同学们可以先回顾一下如何使用 O(sqrt(n)) 的时间找到一个数字 n 的所有因子(C++)。
注释的两个地方是容易出错的地方.
class Solution {
public:
int kthFactor(int n, int k) {
vector<int> factors;
// 使用 i * i <= n，避免 sqrt(n) 运算的性能和精度问题
for(int i = 1; i * i <= n; i ++)
if(n % i == 0){
factors.push_back(i);
// 对于 i * i == n 的情况要进行一下判断，
// 如果 i * i == n，则 i 和 n / i 是一个数字，不能重复添加进 factors
if(i * i != n)
factors.push_back(n / i);
}
// 需要排序
sort(factors.begin(), factors.end());
return k - 1 < factors.size() ? factors[k - 1] : -1;
}
};下面我们可以考虑一下，怎么能避免排序的过程？
其实非常简单。我们在从 i = 1 遍历到 i * i <= n 的过程中，找到的每一个因子 i 都是有序的。所以，如果我们要找的第 k 个因子在这个范围里，可以直接返回。
与此同时，我们找到的每一个因子 n / i 都是倒序的，所以，我们倒序将 n / i 这些因子存在数组中，然后，根据 k 找到它在倒序的数组中出现的位置即可。
以下为我的参考代码(C++):
class Solution {
public:
int kthFactor(int n, int k) {
vector<int> factors;
for(int i = 1; i * i <= n; i ++)
if(n % i == 0){
k --; // 每次 k --
if(!k) return i; // 如果此时 k == 0，就已经找到了这个因子，就是 i
// 倒序存储 n / i。注意，我们还需要对 i * i == n 的情况做判断
if(i * i != n)
factors.push_back(n / i);
}
// 最终，因为 factors 是倒序的
// 我们只需要看在 factors 数组中倒数第 k 个元素就好了
return k - 1 < factors.size() ? factors[factors.size() - k] : -1;
}
};上述算法时间是 O(sqrt(n)) 的，空间是 O(sqrt(n)) 的。因为 factors 最多存储了 sqrt(n) 个约数。
另外，上述算法已经进行了优化。由于我们知道 factors 是倒序的，可以使用线性时间将 factors 翻转过来。因为 factors 里最多有 sqrt(n) 个元素，所以我们可以使用 O(sqrt(n)) 的时间翻转，之后再用 O(1) 的时间拿到第 k 个元素。
这个方法，时间和空间也都是 O(sqrt(n))，但是多了一步翻转数组的过程。
问题来了，我们有没有可能使用 O(1) 的空间完成这个问题？
答案是可以的！但是，我们需要两趟 O(sqrt(n)) 的遍历。
第一趟，从 i = 1 遍历到 i * i <= n，这个过程是在看 i 这个因子；
然后，反向从 i * i > n 的那个 i，遍历回 1，这个过程，再看 n / i 这个因子。
以下为我的参考代码(C++):
class Solution {
public:
int kthFactor(int n, int k) {
int i;
for(i = 1; i * i <= n; i ++)
if(n % i == 0){
k --;
if(!k) return i;
}
i--; // 注意，此时 i * i > n，所以要 i --
// 第二趟反向遍历，对 i 的初始值，还需要根据是否 i * i == n 做判断，避免重复
for(i = (i * i == n ? i - 1 : i); i > 0; i --)
if(n % i == 0){
k --;
if(!k) return n / i; // 看 n / i
}
return -1;
}
};上述算法时间是 O(sqrt(n)) 的，空间是 O(1) 的。
是不是很酷？：）
觉得有帮助请点赞哇！
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 7502 | 11477 | 65.4% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
