找到一个排序的数组的中位数 [英] Finding the median of an unsorted array

问题描述

要找到一个排序的数组的中位数，我们可以做一个最小堆为n个元素O（nlogn）的时间，那么我们就可以通过一个N / 2个元素提取一个获得中位数。但是，这种方法将需要O（nlogn）的时间。

To find the median of an unsorted array, we can make a min-heap in O(nlogn) time for n elements, and then we can extract one by one n/2 elements to get the median. But this approach would take O(nlogn) time.

我们可以做同样的用某种方法在O（n）的时间？如果能，那么请告诉或暗示的某些方法。

Can we do the same by some method in O(n) time? If we can, then please tell or suggest some method.

推荐答案

您可以用中位数算法中位数找到一个排序的数组中的线性时间的中位数。

You can use the Median of Medians algorithm to find median of an unsorted array in linear time.

这篇关于找到一个排序的数组的中位数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！