找到没有排序的未排序数组的位数

Question

是否有找到未排序数组的中值的方法： 1-没有对其进行排序。 2-不使用选择算法，也不使用中位数

我发现了很多类似于我的其他问题。但是大多数解决方案（如果不是全部的话）都讨论了SelectProblem和MedianOfMedians

Answer 1

您当然可以在不对其进行排序的情况下查找数组的中值。不太容易的是有效地做到这一点。

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

或者你可以使用一个最小的堆，它的大小恰好是数组大小的一半。使用阵列元素的前半部分构建堆，然后对于其余每个元素x，如果x大于堆的最小值，则用x替换最小元素。最后，堆的最小元素是中位数。那是O（n log n）时间和O（n）空间。

Answer 2

在http://www.aip.de/groups/soe/local/numres/bookfpdf/f8-5.pdf上描述了一个非破坏性的例行selip（）。它通过数据进行多次传递，在每个阶段随机选择当前值范围内的项目，然后计算项目数量以建立随机选择的等级。

Answer 3

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

我会在这里留下主要想法。有关该算法工作原因的更详细说明和证明，请检查here。

让A成为你的数组，并让n=|A|。让我们假设A的所有元素是不同的。算法如下：

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

算法背后的主要思想是获得两个元件（pl和pr）围绕该中值元素（即pl < m < pr），使得这两个是在有序版本非常接近一个2彼此的数组（并且不需要实际对数组进行排序）。很可能，所有六个步骤只需要执行一次（即，您将从第一次并且仅经过步骤1-5时获得具有这些“良好”属性的pl和pr，因此不会返回到步骤1）。一旦找到两个这样的元素，您可以简单地对它们之间的元素进行排序，并找到中位元素A。

第2步和第5步确实涉及到一些排序（这可能违背了你神秘建立的“规则”：p）。如果在表格中对子数组进行排序，则应使用O(slogs)步骤中执行此操作的某种排序方法，其中s是要排序的数组大小。由于T和M明显小于A，所以排序步骤采用“小于”O(n)步骤。如果它也违反对子数组进行排序的规则，则考虑到在这两种情况下排序并不是真的需要。您只需要找到一种方法来确定pl，pr和m，这只是另一个选择问题（使用各自的索引）。虽然排序T和M确实做到了这一点，但您可以使用任何其他选择方法（可能是前面建议的rici）。