算法 - 如何以O(K)的时间复杂度和O(n)的构建复杂度找到第K个元素

Question

我需要在一个无序包含n个元素的数组中，以O(k)的时间复杂度查找第k个元素，需满足以下需求：

1）构建数据结构的时间复杂度可以为O(n)，可以用给定的数组构建任何你想要的数据结构。

2）以O(k)的时间复杂度查找第k个元素。

- Eldar Shalev

---

欢迎来到 [so]。请花些时间查看 [tour] 和 [ask]。在您的问题中添加任何相关元素，至少尽力包含一个 [mcve]。 - PJProudhon

build O(n) 是什么意思？预处理时间？ - MBo

“kth”元素是什么意思？ - suvojit_007

第k个元素意味着某种顺序。元素如何排序？此外，k == n吗？ - icarus

数据数组中会有重复吗？数据的范围是多少？请提供更多细节。 - Shawn Xiong

Answer 1

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

预处理：

找到中位数元素，并以该元素为枢轴对数组进行划分。然后在较小的一半数组上不断应用此过程，直到剩下一个元素。

每个步骤中的较大一半数组称为 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) 大的元素。使用（确定性变体的）quickselect 算法可以在 O(len(A(n))) 时间内完成。由于 len(A(n)) 是 Theta(k)，因此该元素可以在 O(log k) + O(k) = O(k) 时间内找到。

理解提示：

首先考虑 n 为 2 的幂减一的情况。然后子数组 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 = 4大的元素。为此，我们使用快速选择算法。

- Paul Hankin

---

这个算法的前提是数组中没有重复元素。你能解释一下为什么吗？ - Montoya

@DannyHambourg 如果存在重复元素，当你进行数据透视时，数组的两半可能会失衡。我相信有办法解决这个问题，尽管可能会比较麻烦。但是提问者说没有重复元素，这一点应该是确定的。 - Paul Hankin