查找一个未排序的阵列的中值查找一个未排序的阵列的中值(Finding the median of a

2019-05-14 09:04发布

为了找到一个未排序的阵列的中值,我们可以在O(nlogn)时为n个元素一个最小堆,然后我们可以通过一个n / 2元件中提取一个,以获得中间值。 但是,这种方法将需要O(nlogn)时间。

我们可以做同样的用某种方法在O(n)的时间? 如果能,那么请告诉或建议一些方法。

Answer 1:

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



Answer 2:

我已经upvoted的@dasblinkenlight答案,因为中位数中位数的算法实际上解决了O(n)的时间这个问题。 我只想用堆还补充说,这个问题可以在O(n)的时间来解决。 构建堆可以在O(n)的时间通过自下而上来完成。 看看下面的文章,详细说明堆排序

假设你的阵列具有N个元件,则必须建立两个堆:包含第一N / 2个元素(或(N / 2)+1,如果N是奇数)甲MaxHeap和含有剩余的元素一个MinHeap。 如果N是奇数,那么你的中位数是MaxHeap的()通过获取最大O(1)的最大元素。 如果N是偶数,则你的位数是(MaxHeap.max()+ MinHeap.min())/ 2这需要O(1)也。 因此,整个操作的实际成本是堆建筑操作这是O(n)。

BTW这个MaxHeap / MinHeap算法工作还当你不知道数组元素的数目事先(如果你要解决的整数为如流同样的问题)。 你可以看到有关如何在下面的文章解决此问题的详细信息中位数整数流



Answer 3:

Quickselect工作在O(N),这也是在快速排序的分区步骤中使用。



Answer 4:

快速选择算法可以找到一个阵列的线性的第k个最小的元素( O(n)的运行时间。 这里是一个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)


Answer 5:

它可以在O(n)的使用Quickselect算法,也指k阶统计(随机算法)来完成。



Answer 6:

维基百科说,中值 - - 中位数在理论上是O(N),但在实践中不使用,因为找到“好”枢轴的开销使得它太慢了。
http://en.wikipedia.org/wiki/Selection_algorithm

下面是Java源用于Quickselect算法来寻找在一个数组第k元素:

/**
 * Returns position of k'th largest element of sub-list.
 * 
 * @param list list to search, whose sub-list may be shuffled before
 *            returning
 * @param lo first element of sub-list in list
 * @param hi just after last element of sub-list in list
 * @param k
 * @return position of k'th largest element of (possibly shuffled) sub-list.
 */
static int select(double[] list, int lo, int hi, int k) {
    int n = hi - lo;
    if (n < 2)
        return lo;

    double pivot = list[lo + (k * 7919) % n]; // Pick a random pivot

    // Triage list to [<pivot][=pivot][>pivot]
    int nLess = 0, nSame = 0, nMore = 0;
    int lo3 = lo;
    int hi3 = hi;
    while (lo3 < hi3) {
        double e = list[lo3];
        int cmp = compare(e, pivot);
        if (cmp < 0) {
            nLess++;
            lo3++;
        } else if (cmp > 0) {
            swap(list, lo3, --hi3);
            if (nSame > 0)
                swap(list, hi3, hi3 + nSame);
            nMore++;
        } else {
            nSame++;
            swap(list, lo3, --hi3);
        }
    }
    assert (nSame > 0);
    assert (nLess + nSame + nMore == n);
    assert (list[lo + nLess] == pivot);
    assert (list[hi - nMore - 1] == pivot);
    if (k >= n - nMore)
        return select(list, hi - nMore, hi, k - nLess - nSame);
    else if (k < nLess)
        return select(list, lo, lo + nLess, k);
    return lo + k;
}

我没有列入的比较和交换方法的源,所以很容易更改代码使用Object []而不是双[]的工作。

在实践中,你可以期望上面的代码为O(N)。



Answer 7:

答案是“没有,一个也找不到线性任意时间,未排序的数据集的中位数”。 (因为我知道远)最好有一个可作为一般规则做的是中位数的中位数(得到一个体面的开始),其次是Quickselect。 价:[ https://en.wikipedia.org/wiki/Median_of_medians][1]



文章来源: Finding the median of an unsorted array