找到未排序的未排序数组的中位数

Question

有没有办法找到未排序数组的中位数:1-没有排序它.2-不使用选择算法,也不使用中位数的中位数

我发现了许多类似于我的其他问题.但是解决方案,其中大部分,如果不是全部,都讨论了SelectProblem和MedianOfMedians

Answer 1

您当然可以找到数组的中位数而不对其进行排序.有效的做法并不容易.

例如,您可以迭代数组的元素; 对于每个元素,计算小于等于它的元素数,直到找到具有正确计数的值.这将是O(n ²)时间,但只有O(1)空间.

或者你可以使用一个最小堆,其大小正好是数组大小的一半.使用数组元素的前半部分构建堆,然后对于每个剩余元素2k,如果2k+1大于堆的最小值,则用min替换min元素k+1.最后,堆的最小元素是中位数.那是O(n log n)时间和O(n)空间.

Answer 2

有一种随机算法能够O(n)分步完成此任务（平均情况），但它确实涉及对数组的某些子集进行排序。而且，由于其随机性，无法保证它实际上会完成（尽管这种不幸的事件发生的概率应该为零）。

我将把主要思想留在这里。有关更详细的描述以及该算法为何有效的证明，请查看此处。

让A成为你的数组并让n=|A|. 让我们假设 的所有元素A都是不同的。算法是这样的：

1. 从 中随机选择t = n^(3/4)元素A。
2. 让T为所选元素的“集合”。Sort T。
3. 设置pl = T[t/2-sqrt(n)]和pr = T[t/2+sqrt(n)]。
4. 迭代 的元素A并确定有多少元素小于pl（用 表示l）和有多少元素大于pr（用 表示r）。如果l > n/2或r > n/2，则返回步骤 1。
5. 让为和之间的M元素集。可以在步骤 4 中确定，以防万一我们到达步骤 5。如果 的大小不大于，则排序。否则，返回步骤 1。AplprMM4tM
6. 返回m = M[n/2-l]作为中值元素。

该算法背后的主要思想是获取包围中值元素（即< < ）的两个元素（pl和），使得这两个元素在数组的有序版本中彼此非常接近，一两个（并且在不实际对数组进行排序的情况下执行此操作）大批）。很有可能，所有六个步骤只需要执行一次（即，您将从一开始就获得和 并具有这些“良好”属性，并且只经过步骤 1-5，因此无需返回步骤 1）。一旦找到两个这样的元素，您可以简单地对它们之间的元素进行排序并找到 的中值元素。prplmprplprA

步骤 2 和步骤 5 确实涉及一些排序（这可能违反您神秘建立的“规则”:p）。如果对表中的子数组进行排序，则应使用某种O(slogs)分步执行此操作的排序方法，其中s是要排序的数组的大小。由于T和M明显小于A排序步骤，因此采用“小于”O(n)步骤。如果对子数组进行排序也违反规则，那么请考虑到在这两种情况下都不需要排序。您只需要找到一种方法来确定pl、pr和m，这只是另一个选择问题（具有各自的索引）。在排序T并M完成此操作时，您可以使用任何其他选择方法（也许rici之前建议的方法）。