3

我创建了一个程序来查找数字列表的中位数。数字列表是动态的，因为可以删除和插入数字（可以输入重复的数字），在此期间，重新评估并打印出新的中位数。

我使用多图创建了这个程序，因为

1）它已经被排序的好处，
2）易于插入，删除，搜索（因为多图实现了二进制搜索）
3）允许重复条目。

条目数 + 删除数（表示为 N）的约束为：0 < N <= 100,000。

我编写的程序可以运行并打印出正确的中位数，但速度不够快。我知道 unsorted_multimap 比 multimap 快，但是 unsorted_multimap 的问题是我必须对其进行排序。我必须对其进行排序，因为要找到中位数，您需要一个排序列表。所以我的问题是，使用 unsorted_multimap 然后快速对条目进行排序是否可行，或者这很荒谬？只使用向量、快速排序向量并使用二分搜索会更快吗？或者，也许我忘记了一些我什至没有想到的绝妙解决方案。

虽然我对 C++ 并不陌生，但我承认，我在时间复杂性方面的技能有些平庸。

我越看自己的问题，我就越开始认为仅使用带有快速排序和二进制搜索的向量会更好，因为数据结构基本上已经实现了向量。

4

5 回答 5

5

我越看自己的问题，我就越开始认为仅使用带有快速排序和二进制搜索的向量会更好，因为数据结构基本上已经实现了向量。

如果您只有很少的更新 - 使用未排序的 std::vector + std::nth_element算法，即 O(N)。您不需要完全排序，即 O(N*ln(N))。

nth_element 的现场演示：

#include <algorithm>
#include <iterator>
#include <iostream>
#include <ostream>
#include <vector>

using namespace std;

template<typename RandomAccessIterator>
RandomAccessIterator median(RandomAccessIterator first,RandomAccessIterator last)
{
   RandomAccessIterator m = first + distance(first,last)/2; // handle even middle if needed
   nth_element(first,m,last);
   return m;
}

int main()
{
   vector<int> values = {5,1,2,4,3};
   cout << *median(begin(values),end(values)) << endl;
}

输出是：

3

如果您有很多更新并且只从中间删除，请使用comocomocomocomo 建议的两个堆。如果你会使用fibonacci_heap - 那么你也会得到 O(N) 从任意位置移除（如果没有处理它）。

如果您有很多更新并且需要从任意位置删除 O(ln(N)) - 然后按照ipc 的建议使用两个多重集。

于 2013-03-14T20:03:51.160 回答
3

如果您的目的是动态跟踪中位数，则在插入/删除元素时，您应该使用最小堆和最大堆。每个都包含一半的元素......几天前有一个相关的问题：如何实现中值堆

但是，如果您需要搜索特定值以删除元素，您仍然需要某种映射。

你说它很慢。每次需要中位数时，您是否都从地图的开头迭代到第 (N/2) 个元素？你不需要。您可以通过维护一个始终指向它的迭代器和一个小于该元素数量的计数器来跟踪中值。每次插入/删除时，将新/旧元素与中值进行比较，并更新迭代器和计数器。

另一种看待它的方式是两个多重映射，每个映射包含一半的元素。一个持有小于中位数（或相等）的元素，另一个持有大于中位数的元素。堆更有效地执行此操作，但它们不支持搜索。

如果您只需要几次中位数，您可以使用“选择”算法。它在 Sedgewick 的书中有所描述。平均需要 O(n) 时间。它类似于快速排序，但不完全排序。它只是用随机枢轴对数组进行分区，直到最终它在一侧“选择”较小的 m 个元素 (m=(n+1)/2)。然后你搜索那些 m 个元素中最大的一个，这就是中位数。

于 2013-03-14T20:28:55.403 回答
2

以下是您如何在O(log N)每次更新中实现它：

template <typename T>
class median_set {
public:
  std::multiset<T> below, above;

  // O(log N)
  void rebalance()
  {
    int diff = above.size() - below.size();
    if (diff > 0) {
      below.insert(*above.begin());
      above.erase(above.begin());
    } else if (diff < -1) {
      above.insert(*below.rbegin());
      below.erase(below.find(*below.rbegin()));
    }
  }

public:
  // O(1)
  bool empty() const { return below.empty() && above.empty(); }

  // O(1)
  T const& median() const
  {
    assert(!empty());
    return *below.rbegin();
  }

  // O(log N)
  void insert(T const& value)
  {
    if (!empty() && value > median())
      above.insert(value);
    else
      below.insert(value);
    rebalance();
  }

  // O(log N)
  void erase(T const& value)
  {
    if (value > median())
      above.erase(above.find(value));
    else
      below.erase(below.find(value));
    rebalance();
  }
};

（与测试一起工作）

思路如下：

  • 跟踪两组中高于和低于中位数的值
  • 如果添加了新值，请将其添加到相应的集合中。始终确保下面的集合恰好比另一个多 0 或 1
  • 如果删除了某个值，请将其从集合中删除并确保条件仍然成立。

您不能使用priority_queues ，因为它们不允许您删除一项。

于 2013-03-14T20:33:37.733 回答
2 
Can any one help me what is Space and Time complexity of my following C# program with details.
//Passing Integer array to Find Extreme from that Integer Array
   public int extreme(int[] A)
        {
            int N = A.Length;
            if (N == 0)
            {
                return -1;
            }
            else
            {
                int average = CalculateAverage(A);
                return FindExtremes(A, average);
            }
        }
// Calaculate Average of integerArray
        private int CalculateAverage(int[] integerArray)
        {
            int sum = 0;
            foreach (int value in integerArray)
            {
                sum += value;
            }
            return Convert.ToInt32(sum / integerArray.Length);
        }
//Find Extreme from that Integer Array
        private int FindExtremes(int[] integerArray, int average) {
            int Index = -1; int ExtremeElement = integerArray[0];
            for (int i = 0; i < integerArray.Length; i++)
            {
                int absolute = Math.Abs(integerArray[i] - average);
                if (absolute > ExtremeElement)
                {
                    ExtremeElement = integerArray[i];
                    Index = i;
                }
            }
            return Index;
        }
于 2013-03-16T13:57:11.973 回答
1

几乎可以肯定，使用向量会更好。可能会在中位数计算之间维护要删除的索引的辅助向量，以便您可以批量删除它们。新添加的也可以放入辅助向量中，排序，然后合并。

于 2013-03-14T20:00:01.123 回答