gpt4 book ai didi

算法 - 如何在 O(K) 和构建 O(n) 中找到 Kt'h 元素

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:13:01 27 4
gpt4 key购买 nike

我需要在 O(k) 中找到第 K 个元素,输入的数组具有无序的 n 个元素,满足以下要求:

1) 构建可以是 O(n)(你可以用给定的数组构建你想要的任何数据结构)

2) 在O(k)中找到第k个元素

最佳答案

此算法在假设数组中没有重复元素的情况下有效。

预处理

找到中值元素,并以该元素为轴心数组。然后继续在数组的较小一半上应用此过程,直到您只剩下一个元素。

在每个步骤中调用数组的较大一半 A(m)、A(m-1)、....、A(0) 以获得某些 m。 A(0) 的大小始终为 1,并且每个连续数组的大小要么是前一个数组大小的两倍,要么加一。也就是说,len(A(0)) = 1,len(A(n)) = len(A(n-1)) 或 len(A(n-1))+1。请注意 2^n <= len(A(n)) < 2^(n+1)。

找到长度为 n 的数组的中位数需要 O(n) 时间(使用众所周知的线性时间中位数查找算法),并且旋转也需要 O(n) 时间。您正在递归地应用它(在较小的一侧),这总体上需要 n + n/2 + n/4 + ... = O(n) 时间。

寻找第k个元素

定义 S(n) 为 A(0), A(1), ..., A(n-1) 的长度之和。 (S(0) = 0)。

找到 n 使得 S(n) <= k,并且 S(n+1) > k。您可以在 O(log k) 时间内完成此操作。

然后,找到A(n)中第k-S(n)个最大的元素。这可以使用快速选择算法的(确定性变体)在 O(len(A(n))) 时间内完成。由于len(A(n))是Theta(k),所以在O(log k) + O(k) = O(k)的时间内找到了这个元素。

理解注意事项

首先考虑 n 是 2 减 1 的幂的情况更容易。然后子数组 A(i) 的大小加倍。例如,当 n 为 16,并且输入是按某种顺序排列的数字 0 到 15 时,子数组可能如下所示:

A(0) = [0]
A(1) = [2, 1]
A(2) = [6, 3, 4, 5]
A(3) = [15, 8, 11, 10, 7, 12, 13, 9, 14]

要找到第 7 大元素,我们发现它必须位于 A(2) 中,并且 A(0) 和 A(1) 中有 3 个元素组合在一起,因此我们需要找到 7-3 = 4th 最大的元素A2)。我们使用快速选择来做到这一点。

关于算法 - 如何在 O(K) 和构建 O(n) 中找到 Kt'h 元素,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52944322/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com