时间戳

首页 > 解决方案 > 算法 - 如何在 O(K) 和构建 O(n) 中找到 Kt'h 元素

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

问题描述

我需要在 O(k) 中找到 K 元素，并输入一个具有以下要求的无序 n 元素的数组：

1）构建可以是O（n）（您可以使用给定的数组构建您想要的任何数据结构）

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

标签： algorithmdata-structures

解决方案

假设数组中没有重复的元素，该算法有效。

预处理

找到中间元素，并在该元素上旋转数组。然后继续在数组的较小一半上应用这个过程，直到你只剩下一个元素。

在每个步骤 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) 中的 kS(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 个元素，因此我们需要找到 A(2) 中的第 7-3 = 4th 大元素）。我们使用快速选择来做到这一点。

推荐阅读