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

介绍

最近我写了一篇文章《学习大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) 之间，比前者更好，也更差比后者。这是一个图表：

Mathspace 提供

结论

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

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

祝你学习顺利，下次再见！

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