查找未排序只读数组中的中位数

Question

给定一个包含n元素的只读数组，找到数组中的中位数(按大小计算的第ceiling(n/2)个元素)，O(logn)空间和平均时间O(nlogn)。

• 数组中的元素是不同的。
• 数组未排序。
• 您不能更改数组中的任何值，只能读取它们

我想过使用快速排序的想法，但不更改数组就不可能执行它。复制到另一个阵列将超出所需的空间。

Answer 1

您可以使用分而治之方法解决它，在最小值和最大值之间找到一个随机元素，检查它是否为中位数，中位数是否低于或高于它，并仅在数组的子范围内将问题减小到较小的大小。

1. 将min设置为数组中的最小元素，max设置为最大元素。

2. 选择一个mid范围内的随机数(min < mid < max)，如果没有这样的mid，要么是min，要么是max是中位数，找到哪个就完成了。

3. 检查min、mid或max中的任何一个是中位数(线性搜索，计算有多少个更大/更小)。

   3.1. 如果是这样，您就完成了。

   3.2. 否则，中位数介于(min,mid)或(mid,max)之间，并且您知道在哪里(如果更多高于中或低于它)。

   3.3. 如果是(min,mid)，则设置max = mid，否则设置min = mid。

   3.4. 返回 2.

---

正确性：

• 如果算法找到一个数字 - 停止子句只是由于找到中位数。
• 对于每次迭代，中位数仍然在(min,max)(带归纳的形式证明..)，并且每次迭代的范围保证缩小，因此算法保证停止并产生一些结果。

---

时间复杂度：

• 步骤1：只重复一次，需要O(n)时间。
• 第 2 步：花费O(n)时间(在范围内找到不同的数字)并重复每次迭代。
• 第 3 步：需要O(n)时间(通过每个范围是线性的)。

平均情况下有O(logn)次迭代(类似于二叉搜索推理)。

这给我们带来了O(nlogn)时间的复杂性

---

空间复杂度：

依赖于实现，但使用尾递归(类似于上面的高级伪代码)实际上可以O(1)。对于常规递归，对于堆栈来说，这是O(logn)。

Answer 2

这是一个简单的算法。它包括通过跟踪中位数所在的区间的下限和上限来搜索中位数。

设 E 为元素列表。将中位数的下限和上限 L 和 U 设置为 null。

对于 E 中的每个元素 e，

1. 如果 L 不为空且 e <L，则> U，则 e 不能是中位数，请跳到下一个元素。
2. 扫描 E 并计算 e 之前元素的 B 数和 e 之后元素的 A 数。
3. 如果 A = B，e 是中位数，则终止。如果 A = B + 1，则没有单个中位数，但 e 紧邻中位数点，终止。如果 B = A + 1，则没有单个中位数，但 e 紧跟在中位数之后，终止。
4. 如果 A> B，中位数在 e 之后，则设置 L = e。如果 B> A，中位数在 e 之前，则设置 U = e。

空间复杂度为 O(1)。平均而言，时间复杂度最多为 O(n²) 和 O(nlogn)。

例：

E = [2 4 7 9 0 6 5]
L,U = null,null  Initial state.
e = 2  L,U = 2,null     Update L.
e = 4  L,U = 4,null     Update L.
e = 7  L,U = 4,7        Update U.
e = 9  L,U = 4,7        Skip 9.
e = 0  L,U = 4,7        Skip 0.
e = 6  L,U = 4,6        Update U.
e = 5  Median is 5      Terminate.