当前位置：首页 > article >正文

LeetCode 1492 n的第K个因子

article 2025/3/31 0:32:53

寻找整数的第 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);
    }
}