N 的第 K 个因子 - O(sqrt n) 算法

wufei123 2025-01-05 阅读:10 评论:0

深入探讨o(√n)时间复杂度算法：leetcode因子查找问题本文深入探讨LeetCode一道求解正整数第k个因子的问题，并介绍一种O(√n)时间复杂度的解法，优化了传统的O(n)方法。问题描述给定两个正整数n和k，求n的升序排列因子...

深入探讨o(√n)时间复杂度算法：leetcode因子查找问题

本文深入探讨LeetCode一道求解正整数第k个因子的问题，并介绍一种O(√n)时间复杂度的解法，优化了传统的O(n)方法。

问题描述

给定两个正整数n和k，求n的升序排列因子列表中的第k个因子。若n少于k个因子，则返回-1。

传统O(n)解法

最直观的解法是遍历1到n，检查每个数是否为n的因子。代码如下：

def getkthfactorofn(n, k):
    result = 0
    for i in range(1, n + 1):
        if n % i == 0:
            result += 1
            if result == k:
                return i
    return -1

该方法的时间复杂度为O(n)，效率较低。

优化：利用因子对称性

n的因子具有对称性：如果i是n的因子，则n//i也是n的因子。例如，81的因子为[1, 3, 9, 27, 81]，可以看出3和27，9和9是成对出现的。只有当n是完全平方数时，根号n才会单独出现。

利用此特性，我们只需遍历到√n即可找到所有因子。

O(√n)解法

改进后的代码如下：

import math

def getkthFactorOfN(n, k):
    i = 1
    factors_asc = []
    factors_desc = []
    while i * i <= n:
        if n % i == 0:
            factors_asc.append(i)
            if i * i != n:  #避免重复添加根号n
                factors_desc.insert(0, n // i)
        i += 1

    factors = factors_asc + factors_desc
    if k <= len(factors):
        return factors[k - 1]
    else:
        return -1

代码首先初始化i=1，并创建两个列表factors_asc和factors_desc分别存储升序和降序的因子。循环条件i * i

在循环中，如果i是因子，则将其添加到factors_asc，并判断是否为完全平方数，如果不是，则将n // i添加到factors_desc的头部（保证降序）。

循环结束后，将两个列表合并，如果k小于等于因子总数，则返回第k个因子，否则返回-1。

时间复杂度分析

该方法的时间复杂度为O(√n)，因为循环次数最多为√n。这显著优于O(n)方法，尤其在n值很大的情况下。

进一步优化

为了进一步优化，可以避免使用len()函数，预先计算因子数量，从而将时间复杂度降低为严格的O(√n)。

结论

本文介绍了利用因子对称性优化LeetCode因子查找问题的方法，将时间复杂度从O(n)降低到O(√n)，有效提高了算法效率。该方法充分体现了算法设计中优化技巧的重要性。