LeetCode 1492. n 的第 k 个因子
题目描述
题意分析
将正整数
n的所有正因子按升序排列，返回第k个。因子必须能整除n，排名从一开始；因子总数不足k时返回-1。每个因子只计一次，完全平方数的平方根也不能重复出现。只需要找指定排名，不必保存并排序所有因子。
解法：两趟因子配对枚举
核心思路
[!blue]
如果
factor是因子，n / factor也是因子，两个数至少有一个不大于平方根。因此只检查一到平方根就能找到全部因子对。第一遍将
factor递增，命中的小因子本身已经是升序。每找到一个就将剩余排名k减一，减到零时直接返回。如果小因子还不够，答案就在对应的大因子中。但小因子越大，对应的
n / factor越小，所以第二遍必须从平方根扫描边界向一递减，这样输出的大因子才是升序。非因子在第二遍仍要跳过；若
factor == n / factor，说明两者就是同一个平方根，第一遍已经计过，也要跳过。其他大因子均严格大于第一遍的小因子，所以两遍拼起来正好是完整升序。循环用
factor <= n / factor判断是否在平方根以内，避免通过乘法平方比较；limit保存扫描到的边界，不要求它本身恰好是因子。
解题步骤
- 从一开始枚举小于或等于平方根的候选，记录扫描边界。
- 能整除时将剩余排名减一，归零就返回当前小因子。
- 从记录的边界反向扫到一，跳过非因子和已计过的平方根。
- 每找到一个互补大因子，再将排名减一，归零时返回
n / factor。- 两遍都结束仍未归零，则返回
-1。
代码实现
class Solution {
public int kthFactor(int n, int k) {
// 记录平方根扫描边界，不是已找到的因子数量。
int limit = 0;
for (int factor = 1; factor <= n / factor; factor++) {
limit = factor;
if (n % factor == 0 && --k == 0) {
return factor;
}
}
// 反向扫描小因子，才能按升序得到互补的大因子。
for (int factor = limit; factor >= 1; factor--) {
// 跳过非因子和已经计数的平方根。
if (n % factor != 0 || factor == n / factor) {
continue;
}
if (--k == 0) {
return n / factor;
}
}
return -1;
}
}
func kthFactor(n int, k int) int {
// 记录平方根扫描边界，不是已找到的因子数量。
limit := 0
for factor := 1; factor <= n/factor; factor++ {
limit = factor
if n%factor == 0 {
k--
if k == 0 {
return factor
}
}
}
// 反向扫描小因子，才能按升序得到互补的大因子。
for factor := limit; factor >= 1; factor-- {
// 跳过非因子和已经计数的平方根。
if n%factor != 0 || factor == n/factor {
continue
}
k--
if k == 0 {
return n / factor
}
}
return -1
}
复杂度分析
- 时间复杂度：$O(\sqrt n)$，最多在平方根范围内扫描两遍。
- 空间复杂度：$O(1)$，只保存扫描边界及剩余排名。
关键点总结
[!green]
- 因子配对把枚举范围缩到平方根以内。
- 小因子升序对应大因子降序，反向扫描才能接成完整升序。
- 剩余排名跨两遍连续递减，平方根只计一次。
易错点总结
[!yellow]
- 找到小因子就立即计入互补大因子，会打乱整体大小顺序。
- 完全平方数重复计数平方根，会使后续排名错位。
- 第二遍只检查保存的边界而不重新检查整除，会把非因子也计入。
- 只枚举小因子后直接返回不存在，会漏掉大于平方根的有效答案。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1390. 四因数 | 中等 | 同样按平方根成对枚举因子，本题还需按小因子升序、大因子降序确定第k项。 |
| 507. 完美数 | 简单 | 因子枚举相同，原题求真因子和，本题按大小选择一个因子。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！