LeetCode 1492. n 的第 k 个因子
目录
题目描述
题意分析
给两个正整数
n和k，把n的所有因子（能整除n的正整数）按从小到大排好，返回第k个；如果因子总数不足k个，返回-1。
「因子」的范围要先钉死：包含 1 和
n自身。n = 7的因子是[1, 7]而不是空集或[7]。这个定义直接决定了第 1 个因子恒为 1、最后一个因子恒为n。
「从小到大」是排序要求，但它其实是个免费条件——只要按
1, 2, 3, ...递增的顺序去试除，找到的因子天然就是升序的，完全不需要额外排序。识别出这一点，问题就从「求出所有因子再排序取第 k」简化成「边找边数，数到 k 就停」。
约束里
1 <= k <= n <= 1000。n只有 1000，$O(n)$ 的逐个试除最多 1000 次取模，瞬间完成。但这个范围小得有点刻意——题目下方明确写着一个进阶要求：能否设计时间复杂度小于 $O(n)$ 的算法。面试里问这道题，多半就是奔着这个进阶去的，所以主解法写完之后必须能说出 $O(\sqrt{n})$ 的思路。
边界：
n = 1时因子只有[1]，k = 1返回 1、k = 2返回 -1；n是质数时因子恰好是[1, n]两个；n是完全平方数时，sqrt(n)这个因子只出现一次（它与自己配对），这一点在 $O(\sqrt{n})$ 解法里是必须单独处理的坑；k恰好等于因子总数时返回n自身。
解法：从小到大枚举因子
核心思路
因子成对出现：若 d 整除 n，则
n / d也是因子，并且一对中至少有一个不超过 $\sqrt{n}$。因此只需试除到平方根，就能确定全部因子。小因子按 d 从小到大出现；对应的大因子
n / d却从大到小出现。为了整体升序，先正向扫描输出小因子，再从平方根向 1 反向扫描，输出对应的大因子。完全平方数的平方根在两边相同，第二趟必须跳过。k 作为“还需遇到多少个因子”的计数器，每命中一次就减一，归零时立即返回当前因子。计数不变量是：每次检查候选前，k 始终等于距离目标还需遇到的因子个数。第一趟结束时保存整数平方根上界，供第二趟反向扫描。
正确性说明：每个因子都唯一属于“小于等于平方根的一侧”或其互补的大因子；平方根重复项被显式去除，所以不重不漏。第一趟与第二趟的输出顺序分别递增，且所有小因子不大于所有大因子，因此命中顺序就是全体因子的升序，第 k 次命中即为答案。
解题步骤
- 从 d=1 开始，在
d <= n / d时试除，避免计算d * d可能溢出。- 第一趟每遇到小因子就递减 k，并记录最后检查到的 d 作为平方根上界。
- 从该上界反向扫描；若 d 整除 n 且
d != n / d，则互补因子n / d是尚未输出的大因子。- 第 k 次命中立即返回；两趟结束仍未命中则返回 -1。
n = 12的两趟顺序是1,2,3与4,6,12，k = 3返回 3。n = 16时第二趟跳过重复的 4，因子序列为1,2,4,8,16。质数的第二个因子是自身；k 超过因子总数时返回 -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)$。不保存因子列表。
关键点总结
- 因子配对把枚举上界从 n 降到平方根。
- 小因子正序、大因子需按小因子反序输出，才能得到整体升序。
- 完全平方数的平方根只能计数一次。
- 用
factor <= n / factor代替factor * factor <= n，避免乘法溢出。
易错点总结
- 第二趟仍正向扫描：
n = 12会按12,6,4输出大因子，顺序错误。- 平方根重复计数：
n = 16会得到1,2,4,4,8,16，使k = 4错误返回 4 而不是 8。- 第一趟条件写成
factor < n / factor：会漏掉完全平方数的平方根。- 命中前先判断 k：会产生一位偏移；应在确认是因子后递减，再判断是否归零。
- 循环完返回 0：题目规定因子数量不足时返回 -1。
- 用整数平方根上界却从
limit - 1回扫：非完全平方数可能漏掉最接近平方根的小因子对应的大因子。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 507. 完美数 | 简单 | 要求所有真因子之和，正是配对枚举到 $\sqrt{n}$ 的直接应用，同样要处理平方数 |
| 204. 计数质数 | 中等 | 统计范围内质数个数，用埃氏筛批量标记合数而非逐个试除 |
| 728. 自除数 | 简单 | 判定条件转到「每一位数字都能整除自身」，重点在逐位拆解与 0 的排除 |
| 172. 阶乘后的零 | 中等 | 靠因子 5 的个数直接推导结果，考察把计数问题转成数学公式而非枚举 |
| 69. x 的平方根 | 简单 | 同样围绕 $\sqrt{n}$ 展开，但用二分或牛顿迭代逼近而非枚举 |
| 367. 有效的完全平方数 | 简单 | 判定是否存在整数平方根，可用来练习本题进阶里 d * d == n 的边界判断 |