10

我有一个数组，a = { 1,4,5,6,2,23,4,2}; 现在可以说我必须找到从 2 到 6 的数组位置的中位数（奇数项），所以我所做的，我已经接受a[1]了a[5]，然后我对它进行了排序并将其写arr[0]为中位数。arr[4]arr[2]

但是每次我将值从一个数组放到另一个数组时，我的初始数组的值都保持不变。其次，我已经排序了，所以这个过程要花很多时间**time**。所以我想知道是否有任何方法可以与reduce my computation time.

任何网站，要理解的材料，什么以及如何做？

4

6 回答 6

22

使用O std::nth_element( <algorithm>N)：

nth_element(a, a + size / 2, a + size);
median = a[size/2];
于 2012-06-16T16:56:22.390 回答
15

无需在 O(n) 时间内排序即可找到中位数；执行此操作的算法称为选择算法。

于 2012-06-16T16:15:31.543 回答
6

如果您在同一个数组上执行多个查询，那么您可以使用分段树。它们通常用于执行范围最小/最大值和范围总和查询，但您可以将其更改为范围中位数。

具有 n 个间隔的集合的段树使用 O(n log n) 存储，并且可以在 O(n log n) 时间内构建。范围查询可以在 O(log n) 中完成。

范围段树中的中位数示例：

您自下而上构建分段树（自上而下更新）：

                    [5]
        [3]                     [7]
 [1,2]        [4]         [6]         [8] 
1     2     3     4     5     6     7     8

节点覆盖的索引：

                    [4]
        [2]                     [6]
 [0,1]        [3]         [5]         [7] 
0     1     2     3     4     5     6     7

查询范围索引为 4-6 的中位数将沿着这条值的路径进行：

                    [4]
                          [5]
0     1     2     3     4     5     6     7

搜索中位数，您知道查询中的总元素数 (3)，并且该范围内的中位数将是第二个元素（索引 5）。因此，您实际上是在搜索包含该索引的第一个节点，该索引是具有值 [1,2] 的节点（索引 0,1）。

搜索 3-6 范围的中位数有点复杂，因为您必须搜索恰好位于同一节点中的两个索引 (4,5)。

                    [4]
                                [6]
                          [5] 
0     1     2     3     4     5     6     7

段树

Segment Tree上的范围最小查询

于 2012-06-16T18:08:37.333 回答
1

要找到少于 9 个元素的数组的中位数，我认为最有效的方法是使用像插入排序这样的排序算法。复杂性很差，但是对于这么小的数组，由于k快速排序等更好的算法的复杂性，插入排序非常有效。做你自己的基准测试，但我可以告诉你，插入排序会比 shell 排序或快速排序有更好的结果。

于 2012-06-16T16:21:15.503 回答
0

我认为最好的方法是使用中位数算法计算数组的第 k 个最大元素。您可以在此处找到该算法的总体思路：Java 中的 Median of Median，在维基百科上：http ://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm或只是浏览互联网。在实现过程中可以进行一些一般性的改进（在选择特定数组的中值时避免排序）。但是，请注意，对于少于 50 个元素的数组，使用插入排序比中位数算法更有效。

于 2012-06-16T18:35:39.427 回答
0

在某些情况下，所有现有答案都有一些缺点：

  1. 对整个子范围进行排序并不是很有效，因为不需要对整个数组进行排序来获得中位数，如果要找到多个子范围的中位数，则需要一个额外的数组。
  2. 使用std::nth_element效率更高，但它仍然会改变子范围，因此仍然需要一个额外的数组。
  3. 使用分段树可以获得有效的解决方案，但您需要自己实现结构或使用第三方库。

出于这个原因，我发布了我的方法，该方法使用std::map并受到选择排序算法的启发：

  1. 首先将第一个子范围内元素的频率收集到 的对象中std::map<int, int>。

  2. 有了这个对象，我们可以有效地找到长度为 的子范围的中位数subrangeLength：

    double median(const std::map<int, int> &histogram, int subrangeLength)
{
    const int middle{subrangeLength / 2};
    int count{0};


    /* We use the fact that keys in std::map are sorted, so by simply iterating
       and adding up the frequencies, we can find the median. */
    if (subrangeLength % 2 == 1) {
        for (const auto &freq : histogram) {
            count += freq.second;
            /* In case where subrangeLength is odd, "middle" is the lower integer bound of
               subrangeLength / 2, so as soon as we cross it, we have found the median. */
            if (count > middle) {
                return freq.first;
            }
        }
    } else {
        std::optional<double> medLeft;
        for (const auto &freq : histogram) {
            count += freq.second;
            /* In case where subrangeLength is even, we need to pay attention to the case when
               elements at positions middle and middle + 1 are different. */
            if (count == middle) {
                medLeft = freq.first;
            } else if (count > middle) {
                if (!medLeft) {
                    medLeft = freq.first;
                }
                return (*medLeft + freq.first) / 2.0;
            }
        }
    }

    return -1;
}

  3. 现在，当我们想要获得下一个子范围的中值时，我们只需通过降低要删除的元素的频率来更新直方图，然后为新元素添加/增加它（使用std::map，这是在恒定时间内完成的）。现在我们再次计算中位数并继续此操作，直到我们处理所有子范围。

于 2019-10-18T15:29:05.823 回答