63

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

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

4

10 回答 10

49

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

于 2012-05-19T03:23:58.880 回答
15

我已经支持@dasblinkenlight 的答案，因为中位数算法实际上在 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)。

顺便说一句，当您事先不知道数组元素的数量时，此 MaxHeap/MinHeap 算法也有效（例如，如果您必须为整数流解决相同的问题）。您可以在以下文章整数流的中值中查看有关如何解决此问题的更多详细信息

于 2015-04-11T12:52:36.567 回答
10

快速选择在 O(n) 中工作，这也用于快速排序的分区步骤。

于 2012-05-19T03:24:15.073 回答
10

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)
于 2014-03-31T00:58:51.107 回答
1

答案是“不，无法在线性时间内找到任意未排序数据集的中值”。作为一般规则（据我所知），最好的方法是中位数的中位数（以获得一个不错的开始），然后是快速选择。参考：[ https://en.wikipedia.org/wiki/Median_of_medians][1]

于 2019-04-24T15:26:17.660 回答
0

可以使用 O(n) 中的快速选择算法来完成，请参考 K 阶统计（随机算法）。

于 2012-05-19T08:12:28.503 回答
0

正如维基百科所说，Median-of-Medians 理论上是 o(N)，但在实践中并未使用它，因为寻找“好”枢轴的开销使其太慢。
http://en.wikipedia.org/wiki/Selection_algorithm

这是用于查找数组中第 k 个元素的 Quickselect 算法的 Java 源代码：

/**
 * 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[] 而不是 double[]。

在实践中，您可以期望上述代码为 o(N)。

于 2014-12-31T23:09:13.103 回答
0

让问题成为：在未排序的数组中找到第 K 个最大的元素。

将数组分成 n/5 组，每组由 5 个元素组成。

现在 a1,a2,a3....a(n/5) 代表每组的中位数。

x = 元素 a1,a2,.....a(n/5) 的中位数。

现在，如果 k<n/2，那么我们可以删除中位数大于 x 的组中的最大元素、第二大元素和第三大元素。我们现在可以使用 7n/10 个元素再次调用该函数并找到第 k 个最大值。

否则，如果 k>n/2，那么我们可以删除组中中位数小于 x 的最小、第二小和第三小元素。我们现在可以用 7n/10 个元素再次调用函数并找到第 (k-3n/10) 个最大值。

时间复杂度分析：在大小为 n 的数组中找到第 k 个最大的 T(n) 时间复杂度。

T(n) = T(n/5) + T(7n/10) + O(n)

如果你解决了这个问题，你会发现 T(n) 实际上是 O(n)

n/5 + 7n/10 = 9n/10 < n

于 2020-10-17T07:30:50.180 回答
0

请注意，构建堆实际上需要 O(n) 而不是 O(nlogn)，您可以使用摊销分析来检查这一点，或者只需在 Youtube 中进行检查。Extract-Min 需要 O(logn)，因此，提取 n/2 将花费 (nlogn/2) = O(nlogn) 摊销时间。

关于您的问题，您可以简单地查看Median of Medians。

于 2021-06-16T19:43:41.693 回答
-1

给定两个大小分别为m和n的排序数组nums1和nums2，返回两个排序数组的中位数。

示例 1：

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

代码：

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        merged_array = sorted(nums1 + nums2)
        if len(merged_array) % 2 == 0:
            index = int(len(merged_array)/2)
            output =  (merged_array[index - 1] +  merged_array[index])/2
        else: 
            index = int(len(merged_array)/2)
            output = merged_array[index]
        return output
于 2021-04-19T08:30:55.973 回答