Medium
题目描述
给你两个正整数 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 。
提示：
1 <= k <= n <= 1000
进阶： 你能设计时间复杂度小于 O(n) 的算法吗？
解题思路
解法一：暴力枚举（推荐）
最直观的方法是从 1 到 n 依次检查每个数是否为 n 的因子。当找到第 k 个因子时返回该数，如果遍历完所有数都没找到第 k 个因子则返回 -1。
解法二：优化枚举（进阶）
观察到因子总是成对出现的：如果 i 是 n 的因子，那么 n/i 也是 n 的因子。因此我们只需要遍历到 √n，同时收集因子对。需要注意完全平方数的情况，避免重复计算 √n。
对于数据规模 n ≤ 1000，暴力解法已经足够高效。优化解法的优势在更大数据规模时更明显。
具体实现：
- 暴力法：遍历 1 到 n，计数因子个数，返回第 k 个
- 优化法：遍历 1 到 √n，收集所有因子并排序，返回第 k 个
由于题目数据规模较小，这里推荐使用简洁易懂的暴力解法。
代码实现
class Solution {
public:
int kthFactor(int n, int k) {
int count = 0;
for (int i = 1; i <= n; i++) {
if (n % i == 0) {
count++;
if (count == k) {
return i;
}
}
}
return -1;
}
};
class Solution:
def kthFactor(self, n: int, k: int) -> int:
count = 0
for i in range(1, n + 1):
if n % i == 0:
count += 1
if count == k:
return i
return -1
public class Solution {
public int KthFactor(int n, int k) {
int count = 0;
for (int i = 1; i <= n; i++) {
if (n % i == 0) {
count++;
if (count == k) {
return i;
}
}
}
return -1;
}
}
/**
* @param {number} n
* @param {number} k
* @return {number}
*/
var kthFactor = function(n, k) {
let factors = [];
for (let i = 1; i <= Math.sqrt(n); i++) {
if (n % i === 0) {
factors.push(i);
if (i !== n / i) {
factors.push(n / i);
}
}
}
factors.sort((a, b) => a - b);
return k <= factors.length ? factors[k - 1] : -1;
};
复杂度分析
| 复杂度 | 暴力解法 | 优化解法 |
|---|---|---|
| 时间复杂度 | O(n) | O(√n) |
| 空间复杂度 | O(1) | O(√n) |