在一个未排序的只读数组中找到中位数。

Question

给定一个只读数组，包含n个元素，找到该数组的中位数（按大小排列为第ceiling(n/2)个元素），要求空间复杂度为O(logn)，平均时间复杂度为O(nlogn)。

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

我考虑使用快速排序的思想，但是在不更改数组的情况下执行此操作是不可能的。将其复制到另一个数组中会超出所需的空间。

- Robert

---

我不确定你的意思，但是我需要将所有元素插入到两个堆中，这将占用O(n)的空间。 - Robert

投票重新开放。目前的写法很难确定你在问什么问题陈述非常清晰。原帖作者展示了他的两种方法，并解释了它们为什么失败（证明了自己进行了研究）。如果有一个关闭投票者能够解释他们的理由，那将会很高兴。 - amit

@amit 我正想问同样的问题，我想要一个在给定数组中不改变原有顺序的找到中位数的算法，我不知道为什么他们关闭了这个问题！！ - Holy semicolon

Answer 1

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

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

2. 在(min,max)范围内选择一个随机数mid，如果没有这样的mid，则min或max是中位数，找出哪个是就行了。

3. 检查min、mid或max中是否有中位数（线性搜索，计算有多少个元素比中位数大/小）。

3.1 如果是，则已经完成。

3.2 否则，中位数在（min,mid）或（mid,max）之间，并且你知道其中哪个区间包含中位数（如果有更多的元素大于mid或小于它）。

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)，对于栈来说。

- amit

---

谢谢你的回答。 你能再解释一下为什么栈需要另外一个O(logn)的内存吗？ - Robert

@Robert 这个解决方案需要 O(1) 的额外内存，但如果你将其转移到递归调用中，并且没有将其优化为尾递归，则会有 O(logn) 个递归调用，每个调用都会将一些变量推入调用栈，这将给你带来 O(logn) 的空间。 - amit

Answer 2

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

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

对于E中的每个元素e，

1. 如果L不为null且e < L，则e不能是中位数，请跳到下一个元素。如果U不为null且e > 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.

- RobertBaron

---

这似乎是amit提出的算法的难以阅读的版本，比后者晚发布20分钟。 - tucuxi

@tucuxi 嗯，也许吧，但它更加详细。amit只给出了高层次的步骤。我建议的算法可能更容易实现。 - RobertBaron