查找未排序数组的中位数

Question

为了找到未排序数组的中位数,我们可以在O(nlogn)时间内为n个元素创建一个最小堆,然后我们可以逐个提取n/2个元素来获得中值.但这种方法需要O(nlogn)时间.

我们可以在O(n)时间内通过某种方法做同样的事情吗？如果可以的话,请告诉或建议一些方法.

Answer 1

您可以使用Median of Medians算法在线性时间内查找未排序数组的中位数.

Answer 2

我已经提出了@dasblinkenlight答案,因为Medians of Medians算法实际上在O(n)时间内解决了这个问题.我只想补充说,这个问题可以通过使用堆来在O(n)时间内解决.通过使用自下而上的方法,可以在O(n)时间内构建堆.请查看以下文章,了解堆排序的详细说明

假设您的数组有N个元素,则必须构建两个堆:包含前N/2个元素的MaxHeap(如果N为奇数,则为(N/2)+1)和包含其余元素的MinHeap.如果N是奇数,则中位数是MaxHeap的最大元素(通过获得最大值,O(1)).如果N是偶数,那么你的中位数是(MaxHeap.max()+ MinHeap.min())/ 2这也需要O(1).因此,整个操作的实际成本是堆积构建操作,即O(n).

BTW这个MaxHeap/MinHeap算法也适用于您事先不知道数组元素的数量(如果您必须为例如整数流解决相同的问题).您可以在下面的文章中间整数流中查看有关如何解决此问题的更多详细信息

Answer 3

Quickselect在O(n)中工作,这也用在Quicksort的分区步骤中.

Answer 4

快速选择算法可以在线性(O(n))运行时间中找到数组的第k个最小元素.这是python中的一个实现:

import random

def partition(L, v):
    smaller = []
    bigger = []
    for val in L:
        if val < v: smaller += [val]
        if val > v: bigger += [val]
    return (smaller, [v], bigger)

def top_k(L, k):
    v = L[random.randrange(len(L))]
    (left, middle, right) = partition(L, v)
    # middle used below (in place of [v]) for clarity
    if len(left) == k:   return left
    if len(left)+1 == k: return left + middle
    if len(left) > k:    return top_k(left, k)
    return left + middle + top_k(right, k - len(left) - len(middle))

def median(L):
    n = len(L)
    l = top_k(L, n / 2 + 1)
    return max(l)