LeetCode 1492. n 的第 k 个因子

Categories:

题目描述
思路分析
1. 解法一：枚举因子（推荐）
2. 解法二：枚举到 √n 优化
相似题目

题目描述

✅ 1492. n 的第 k 个因子

思路分析

解法一：枚举因子（推荐）

核心思路：

从 1 到 n 依次枚举所有整数 i，若 n % i == 0 则 i 是 n 的因子

每找到一个因子就将计数器减 1，当计数器归零时返回当前因子

若枚举完仍未找到第 k 个因子，返回 -1

复杂度分析：

时间复杂度：O(n)，其中 n 为给定整数

空间复杂度：O(1)，只使用常数空间

class Solution {
    public int kthFactor(int n, int k) {
        // 从 1 枚举到 n，收集因子
        for (int i = 1; i <= n; i++) {
            if (n % i == 0) {
                k--;

                // 找到第 k 个因子时直接返回
                if (k == 0) {
                    return i;
                }
            }
        }

        return -1;
    }
}

func kthFactor(n int, k int) int {
    // 从 1 枚举到 n，收集因子
    for i := 1; i <= n; i++ {
        if n%i == 0 {
            k--

            // 找到第 k 个因子时直接返回
            if k == 0 {
                return i
            }
        }
    }

    return -1
}

解法二：枚举到 √n 优化

核心思路：

因子总是成对出现：若 i 是 n 的因子，则 n/i 也是因子

只需枚举 1 到 √n 范围内的因子，另一半因子为 n/i（逆序）

先从小到大找前半部分因子，再从大到小找后半部分因子（避免重复）

复杂度分析：

时间复杂度：O(√n)，其中 n 为给定整数

空间复杂度：O(√n)，存储前半部分因子

class Solution {
    public int kthFactor(int n, int k) {
        // 收集 1 到 sqrt(n) 范围内的因子
        List<Integer> factors = new ArrayList<>();
        for (int i = 1; (long) i * i <= n; i++) {
            if (n % i == 0) {
                factors.add(i);
            }
        }

        int size = factors.size();

        // 前半部分因子（升序），直接按序检查
        if (k <= size) {
            return factors.get(k - 1);
        }

        // 后半部分因子（降序）：n/factors[size-1-j]
        k -= size;
        for (int j = size - 1; j >= 0; j--) {
            int factor = factors.get(j);

            // 避免重复计算完全平方根
            if ((long) factor * factor == n) {
                continue;
            }

            k--;
            if (k == 0) {
                return n / factor;
            }
        }

        return -1;
    }
}

func kthFactor(n int, k int) int {
    // 收集 1 到 sqrt(n) 范围内的因子
    factors := []int{}
    for i := 1; i*i <= n; i++ {
        if n%i == 0 {
            factors = append(factors, i)
        }
    }

    size := len(factors)

    // 前半部分因子（升序），直接按序检查
    if k <= size {
        return factors[k-1]
    }

    // 后半部分因子（降序）：n/factors[size-1-j]
    k -= size
    for j := size - 1; j >= 0; j-- {
        factor := factors[j]

        // 避免重复计算完全平方根
        if factor*factor == n {
            continue
        }

        k--
        if k == 0 {
            return n / factor
        }
    }

    return -1
}

相似题目

题目	难度	考察点
1390. 四因数	中等	数学、因子枚举
507. 完美数	简单	因子枚举
2427. 公因子的数目	简单	数学、因子枚举
1362. 最接近的因数	中等	因子枚举
829. 连续整数求和	困难	数学、因子分解
952. 按公因数计算最大组件大小	困难	数学、并查集

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/85886952