查找未排序数组的中位数
求一个未排序数组的中值，我们可以对n个元素做O(nlogn)时间的min-heap，然后我们可以逐个抽取n/2个元素得到中值。但是这种方法需要O(nlogn)时间。
我们能在O(n)时间内通过某种方法做同样的事情吗？如果可以，那么请告诉或建议一些方法。
共有3个答案
Quickselect在O（n）中工作，这也用于Quickort的分区步骤。
我已经投票赞成@dasblinkenlight的答案，因为中位数算法实际上在O(n)时间内解决了这个问题。我只想补充一点，这个问题也可以通过使用堆在O(n)时间内解决。使用自底向上可以在O(n)时间内完成堆的构建。关于堆排序的详细解释，请看下面的文章
假设您的数组有N个元素，您必须构建两个堆:一个包含前N/2个元素的MaxHeap(如果N是奇数，则为(N/2) 1)和一个包含其余元素的MinHeap。如果N是奇数，那么您的中值就是MaxHeap的最大元素(通过获取max得到O(1))。如果N是偶数，那么你的中值是(MaxHeap.max() MinHeap.min())/2这也需要O(1)。因此，整个操作的实际成本是O(n)的堆构建操作。
顺便说一句，当您事先不知道数组元素的数量时，这个MaxHeap/MinHeap算法也可以工作(例如，如果您必须解决整数流的相同问题)。您可以在下面的文章整数流的中值中看到关于如何解决这个问题的更多细节
您可以使用Median of Medians算法在线性时间内找到未排序数组的中位数。
-
这是来自coursera的算法课程中的实践问题;我被困了几个星期。 问题在于：＜code＞给定一个由n个不同的未排序元素x＜sub＞1＜/sub＞组成的数组，x＜sub＞2＜/sub＞，…，x＜sub＞n＜/次级＞ε，加权中值是一个元素xk，对于该元素，值小于xk的所有元素的总权重最多为（总权重）/2，值大于xk的元素的总重量最多为（总重）/2。观察最多有两个加权值。演示如何在O（n）最坏时间内计
-
我试图从Java中未排序的数组中找到中位数。首先，我需要使用选择排序技术对数组进行排序，并且我不能使用任何Java库方法进行排序（因此没有Arrays.sort（array））。另外，我也不能对整个数组进行排序。我只能对尽可能多的元素进行排序，以找到数组的中位数。我想对于一个偶数组，它只是元素的一半加一（然后找到最后两个元素的平均值），而对于一个奇数组，它只会是元素的一半（最后一个是中位数）。 因
-
我试图找到给定排序数组的最大K数。 ex：输入- 到目前为止，我编写的代码返回最大的K元素，但它需要返回最大的K数字。任何帮助都将不胜感激。
-
我想在未排序列表中找到近似中位数，我知道两种算法 算法1-快速选择 算法 2 - 中位数的中位数 我不能在我的项目中使用快速选择，因为它在最坏的情况下需要O(n^2。我听说过中位数，但我的同事建议它需要O(n)和一些常数因子，因此它的时间复杂度是Cn，常数因子比quickselect大。我想知道与中位数相关的常数因子是什么？为什么中位数不使用9元素的伪中位数？< br >或者，他们是否有任何其他算
-
给定一个未排序的数组，我试图找到最接近数组中位数的 K 个元素。我在线性运行时间内找不到解决方案。 这里的中位数是6。 答案是2,3,4,5,6。 任何帮助或提示将不胜感激。
-
经过仔细的研究和思考，我决定发布这个问题，这是我今天早些时候提出的上一个问题的“续集”。 我做了一个算法，可以找到ArrayList的中值，基本上我所做的就是创建一个临时ArrayList，然后使用集合。在那个ArrayList上，我可以很容易地得到中值。问题是，对于较大的文件来说需要花费太长的时间，我正在尝试（运气不佳）找到一种算法的实现，以获得未排序数组（或ArrayList）的中值。 从我在