首页 后端开发 Python教程 N 的第 K 个因子 - O(sqrt n) 算法

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

Jan 04, 2025 pm 06:29 PM

介绍

最近我写了一篇文章《学习大O符号》一劳永逸。在那篇文章中,我回顾了 Big-O 备忘单中提供的所有类型的 Big O 时间表示法。我认为除了这七个时间符号之外,不可能有更多的时间符号。

仿佛宇宙本身在羞辱我、嘲笑我的无知,我遇到了一道 LeetCode 问题,其解法需要 O(√n) 时间。 如果你疯了,这可以翻译成 O(N^1/2)

问题

给你两个正整数 n 和 k。整数 n 的因子被定义为整数 i,其中 n % i == 0。

考虑按升序排列的 n 的所有因子的列表,返回此列表中的第 k 个因子,如果 n 少于 k 个因子,则返回 -1。

显而易见的解决方案

好吧,如果你像我一样,你的第一个想法就是遍历从 1 到 n 的每个数字,检查它是否是一个因子,如果它在所需的 k 索引中,则返回它。

代码如下所示:

def getkthFactorOfN(n, k):
    result = 0
    for i in range(1, n + 1):
        if n % i == 0:
            result = result + 1
            if result == k:
                return i
    return -1
登录后复制

这一切都很好,但它是“仅” O(n)。毕竟,只有一个循环,并且最多可达 n 1。
考虑时间符号时,所有其他操作都会被丢弃。

但是,我的朋友,有一个问题。

了解因素

如果你仔细想想,因素在某个点之后就会“镜像”。

以数字 81 为例,它的因数为 [1, 3, 9, 27],其中:

  • 1 * 81 = 81
  • 3 * 27 = 81
  • 9 * 9 = 81
  • 27 * 3 = 81
  • 81 * 1 = 81

如果不算数字9,则操作只是重复和翻转。如果将 n 除以它的一个因数,就会得到另一个因数。
期望 n 的平方根,即它本身的平方(废话)。

有了这些知识,我们现在知道我们不需要迭代循环最多 n 次(范围(1, n 1)),而只需迭代到 math.sqrt(n) 即可。之后,我们就得到了我们需要的所有因素!

不太明显的解决方案

现在我们已经拥有了所需的一切,我们需要将这个循环从 1 -> 转换为 1 -> 。 n 至 1 ->开方 n.

我只是将代码放在这里,我们将逐行检查这些行。

def getkthFactorOfN(n, k):
    i = 1
    factors_asc = []
    factors_desc = []
    while i * i <= n:
        if n % i == 0:
            factors_asc.append(i)
            if i != n // i:
                factors_desc.append(n // i)
        i += 1
    if k <= len(factors_asc):
        return factors_asc[k-1]
    k -= len(factors_asc)
    if k <= len(factors_desc):
        return factors_desc[-k]
    return -1
登录后复制

哦,这要复杂得多。让我们来分解一下:

首先,我们初始化 i = 1。在搜索因子时,该变量将用作“我们当前所在的数字”。

其次,我们将创建两个数组:factors_asc 和 Factors_desc。这里的神奇之处在于,我们将向 Factors_asc 添加因子 - 它们如此命名是因为它们会自动按升序排列。
每当我们向factors_asc添加一些内容时,我们都会将n除以它并将其添加到factors_desc。类似的逻辑在这里;它们将按降序方便地添加。

然后,我们开始循环。在这里,我将其更改为 while i * i

我们首先检查当前数字是否是一个因子 (n % i == 0)。如果是这样,我们可以将其附加到我们的 Factors_asc 数组中。

接下来,我们得到 i 的“逆因子”。我们可以通过检查 i != n // i 是否,或者换句话说,它是否不是根来做到这一点。这是因为根不能在两个数组中重复。如果不是,我们通过运行 n // i 并将结果附加到 Factors_desc 中来获得反转的因子。

之后,我们将 i 加 1 并继续循环。

循环完成后,我们必须获得所需的所有阶乘。

我们首先通过 if k

如果不是,我们必须减去从 k 中找到的因子数量并再次检查 - k -= len(factors_asc) 并且 k

如果 k 在 Factors_desc 内,则使用 Factors_desk[-k] 获取其值(从最后到第一个)。

如果全部失败,返回-1。

曲线

如果你想知道它落在曲线图中的哪个位置,它会在 O(n)O(log n) 之间,比前者更好,也更差比后者。这是一个图表:

The Kth factor of N - an O(sqrt n) algorithm
Mathspace 提供

结论

这是一次发现和研究的旅程。非常感谢您阅读到目前为止。

如果你想更优化,你可以创建factors_asc_len和factors_desc_len变量,并在每次向这些数组追加值时加1,这样就不必调用方法len(),因为该方法是O(n) 因此它会影响时间符号。

祝你学习顺利,下次再见!

以上是N 的第 K 个因子 - O(sqrt n) 算法的详细内容。更多信息请关注PHP中文网其他相关文章!

本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

Video Face Swap

Video Face Swap

使用我们完全免费的人工智能换脸工具轻松在任何视频中换脸!

热门文章

<🎜>:泡泡胶模拟器无穷大 - 如何获取和使用皇家钥匙
3 周前 By 尊渡假赌尊渡假赌尊渡假赌
北端:融合系统,解释
3 周前 By 尊渡假赌尊渡假赌尊渡假赌
Mandragora:巫婆树的耳语 - 如何解锁抓钩
3 周前 By 尊渡假赌尊渡假赌尊渡假赌

热工具

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

热门话题

Java教程
1666
14
CakePHP 教程
1426
52
Laravel 教程
1328
25
PHP教程
1273
29
C# 教程
1255
24
Python:游戏,Guis等 Python:游戏,Guis等 Apr 13, 2025 am 12:14 AM

Python在游戏和GUI开发中表现出色。1)游戏开发使用Pygame,提供绘图、音频等功能,适合创建2D游戏。2)GUI开发可选择Tkinter或PyQt,Tkinter简单易用,PyQt功能丰富,适合专业开发。

Python与C:学习曲线和易用性 Python与C:学习曲线和易用性 Apr 19, 2025 am 12:20 AM

Python更易学且易用,C 则更强大但复杂。1.Python语法简洁,适合初学者,动态类型和自动内存管理使其易用,但可能导致运行时错误。2.C 提供低级控制和高级特性,适合高性能应用,但学习门槛高,需手动管理内存和类型安全。

Python和时间:充分利用您的学习时间 Python和时间:充分利用您的学习时间 Apr 14, 2025 am 12:02 AM

要在有限的时间内最大化学习Python的效率,可以使用Python的datetime、time和schedule模块。1.datetime模块用于记录和规划学习时间。2.time模块帮助设置学习和休息时间。3.schedule模块自动化安排每周学习任务。

Python vs.C:探索性能和效率 Python vs.C:探索性能和效率 Apr 18, 2025 am 12:20 AM

Python在开发效率上优于C ,但C 在执行性能上更高。1.Python的简洁语法和丰富库提高开发效率。2.C 的编译型特性和硬件控制提升执行性能。选择时需根据项目需求权衡开发速度与执行效率。

Python标准库的哪一部分是:列表或数组? Python标准库的哪一部分是:列表或数组? Apr 27, 2025 am 12:03 AM

pythonlistsarepartofthestAndArdLibrary,herilearRaysarenot.listsarebuilt-In,多功能,和Rused ForStoringCollections,而EasaraySaraySaraySaraysaraySaraySaraysaraySaraysarrayModuleandleandleandlesscommonlyusedDduetolimitedFunctionalityFunctionalityFunctionality。

Python:自动化,脚本和任务管理 Python:自动化,脚本和任务管理 Apr 16, 2025 am 12:14 AM

Python在自动化、脚本编写和任务管理中表现出色。1)自动化:通过标准库如os、shutil实现文件备份。2)脚本编写:使用psutil库监控系统资源。3)任务管理:利用schedule库调度任务。Python的易用性和丰富库支持使其在这些领域中成为首选工具。

学习Python:2小时的每日学习是否足够? 学习Python:2小时的每日学习是否足够? Apr 18, 2025 am 12:22 AM

每天学习Python两个小时是否足够?这取决于你的目标和学习方法。1)制定清晰的学习计划,2)选择合适的学习资源和方法,3)动手实践和复习巩固,可以在这段时间内逐步掌握Python的基本知识和高级功能。

Python vs. C:了解关键差异 Python vs. C:了解关键差异 Apr 21, 2025 am 12:18 AM

Python和C 各有优势,选择应基于项目需求。1)Python适合快速开发和数据处理,因其简洁语法和动态类型。2)C 适用于高性能和系统编程,因其静态类型和手动内存管理。

See all articles