寻找整数的第 K 个因子：算法解析与优化
问题描述
给定两个正整数 n 和 k，找到整数 n 的第 k 个因子（升序排列）。若因子数量不足 k，返回 -1。
示例
- 输入：
n=12, k=3
输出：3（因子：1, 2, 3, 4, 6, 12） - 输入：
n=7, k=2
输出：7（因子：1, 7） - 输入：
n=4, k=3
输出：-1（因子：1, 2, 4）
思路分析
方法一：暴力遍历（O (n)）
- 遍历检查：从 1 到
n遍历每个数，判断是否为因子。 - 计数匹配：维护因子计数器，找到第
k个时返回。
代码实现（Java）
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;
}
}
复杂度分析
- 时间复杂度：O (n)，遍历所有可能的因子。
- 空间复杂度：O (1)，仅使用常数额外空间。
方法二：优化遍历（O√n）
核心观察：因子成对出现（如 i 和 n/i）。只需遍历到 √n，分别处理小因子和大因子。
- 收集小因子：遍历 1 到 √n，收集所有小因子（≤√n）。
- 处理大因子：若小因子数量为
m，则大因子数量为m（除非n是平方数，此时中间因子单独存在）。 - 分情况查找：
- 若
k ≤ m：第k个因子在小因子中。 - 否则：第
k-m个因子在大因子中（倒序查找）。
- 若
代码实现（Java）
class Solution {
public int kthFactor(int n, int k) {
List<Integer> smallFactors = new ArrayList<>();
int sqrt = (int) Math.sqrt(n);
// 收集小因子（≤√n）
for (int i = 1; i <= sqrt; i++) {
if (n % i == 0) {
smallFactors.add(i);
}
}
int m = smallFactors.size();
// 情况1：k在小因子范围内
if (k <= m) return smallFactors.get(k-1);
// 情况2：处理大因子（>√n）
int remaining = k - m;
// 检查是否有重复的中间因子（n是平方数）
if (smallFactors.get(m-1) * smallFactors.get(m-1) == n) {
m--; // 中间因子已计入小因子，大因子数量减1
}
// 大因子数量不足
if (remaining > m) return -1;
// 大因子倒序：n/1, n/2, ..., n/(m)
return n / smallFactors.get(m - remaining);
}
}
复杂度分析
- 时间复杂度：O (√n)，仅遍历到平方根。
- 空间复杂度：O (√n)，存储小因子列表（最坏情况：n 是质数，存储 1 个元素）。
优化对比
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 暴力遍历 | O(n) | O(1) | n 较小（如 ≤1e5） |
| 优化遍历 | O(√n) | O(√n) | n 较大（如 ≥1e9） |
边界情况处理
- k 超过总因子数：返回 -1。
- n 是平方数：中间因子（如 4 的因子 2）仅需计算一次。
- k 恰好等于小因子数量：直接返回最后一个小因子。
测试用例
| n | k | 输出 | 因子列表 |
|---|---|---|---|
| 12 | 3 | 3 | [1, 2, 3, 4, 6, 12] |
| 7 | 2 | 7 | [1, 7] |
| 4 | 3 | -1 | [1, 2, 4] |
| 9 | 3 | 9 | [1, 3, 9] |
总结
- 暴力法：简单直观，适合小规模数据。
- 优化法：利用因子成对特性，大幅减少遍历次数，适合大规模数据。
- 关键优化点：分治小因子和大因子，避免重复计算。
扩展思考
- 预处理因子：若需多次查询，可预先缓存因子列表。
- 并行处理：分布式计算中，可拆分因子查找任务。
完整代码可在 GitHub Gist 查看。
博客结构说明
- 问题描述：明确输入输出及示例。
- 思路分析：分步解释暴力法和优化法。
- 代码实现：提供两种方法的完整代码。
- 复杂度对比：表格化展示性能差异。
- 边界处理：强调容易忽略的特殊情况。
- 测试用例：验证逻辑正确性。
- 总结扩展：归纳方法适用场景，提出优化方向。
此结构兼顾了初学者的理解（暴力法）和进阶需求（优化法），通过代码注释和分步解析，帮助读者逐步掌握因子查找的核心逻辑。