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

wufei123 2025-01-05 阅读:5 评论: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的因子。代码如下:

PHP
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)解法

改进后的代码如下:

PHP
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),有效提高了算法效率。 该方法充分体现了算法设计中优化技巧的重要性。

N 的第 K 个因子 - O(sqrt n) 算法 *数学函数图像*

以上就是N 的第 K 个因子 - O(sqrt n) 算法的详细内容,更多请关注知识资源分享宝库其它相关文章!

版权声明

本站内容来源于互联网搬运,
仅限用于小范围内传播学习,请在下载后24小时内删除,
如果有侵权内容、不妥之处,请第一时间联系我们删除。敬请谅解!
E-mail:dpw1001@163.com

分享:

扫一扫在手机阅读、分享本文

发表评论
热门文章
  • 华为 Mate 70 性能重回第一梯队 iPhone 16 最后一块遮羞布被掀

    华为 Mate 70 性能重回第一梯队 iPhone 16 最后一块遮羞布被掀
    华为 mate 70 或将首发麒麟新款处理器,并将此前有博主爆料其性能跑分将突破110万,这意味着 mate 70 性能将重新夺回第一梯队。也因此,苹果 iphone 16 唯一能有一战之力的性能,也要被 mate 70 拉近不少了。 据悉,华为 Mate 70 性能会大幅提升,并且销量相比 Mate 60 预计增长40% - 50%,且备货充足。如果 iPhone 16 发售日期与 Mate 70 重合,销量很可能被瞬间抢购。 不过,iPhone 16 还有一个阵地暂时难...
  • 酷凛 ID-COOLING 推出霜界 240/360 一体水冷散热器,239/279 元

    酷凛 ID-COOLING 推出霜界 240/360 一体水冷散热器,239/279 元
    本站 5 月 16 日消息,酷凛 id-cooling 近日推出霜界 240/360 一体式水冷散热器,采用黑色无光低调设计,分别定价 239/279 元。 本站整理霜界 240/360 散热器规格如下: 酷凛宣称这两款水冷散热器搭载“自研新 V7 水泵”,采用三相六极马达和改进的铜底方案,缩短了水流路径,相较上代水泵进一步提升解热能力。 霜界 240/360 散热器的水泵为定速 2800 RPM 设计,噪声 28db (A)。 两款一体式水冷散热器采用 27mm 厚冷排,...
  • 惠普新款战 99 笔记本 5 月 20 日开售:酷睿 Ultra / 锐龙 8040,4999 元起

    惠普新款战 99 笔记本 5 月 20 日开售:酷睿 Ultra / 锐龙 8040,4999 元起
    本站 5 月 14 日消息,继上线官网后,新款惠普战 99 商用笔记本现已上架,搭载酷睿 ultra / 锐龙 8040处理器,最高可选英伟达rtx 3000 ada 独立显卡,售价 4999 元起。 战 99 锐龙版 R7-8845HS / 16GB / 1TB:4999 元 R7-8845HS / 32GB / 1TB:5299 元 R7-8845HS / RTX 4050 / 32GB / 1TB:7299 元 R7 Pro-8845HS / RTX 2000 Ada...
  • Nginx服务器的HTTP/2协议支持和性能提升技巧介绍

    Nginx服务器的HTTP/2协议支持和性能提升技巧介绍
    Nginx服务器的HTTP/2协议支持和性能提升技巧介绍 引言:随着互联网的快速发展,人们对网站速度的要求越来越高。为了提供更快的网站响应速度和更好的用户体验,Nginx服务器的HTTP/2协议支持和性能提升技巧变得至关重要。本文将介绍如何配置Nginx服务器以支持HTTP/2协议,并提供一些性能提升的技巧。 一、HTTP/2协议简介:HTTP/2协议是HTTP协议的下一代标准,它在传输层使用二进制格式进行数据传输,相比之前的HTTP1.x协议,HTTP/2协议具有更低的延...
  • python怎么调用其他文件函数

    python怎么调用其他文件函数
    在 python 中调用其他文件中的函数,有两种方式:1. 使用 import 语句导入模块,然后调用 [模块名].[函数名]();2. 使用 from ... import 语句从模块导入特定函数,然后调用 [函数名]()。 如何在 Python 中调用其他文件中的函数 在 Python 中,您可以通过以下两种方式调用其他文件中的函数: 1. 使用 import 语句 优点:简单且易于使用。 缺点:会将整个模块导入到当前作用域中,可能会导致命名空间混乱。 步骤:...