如何跟踪整数变化向量的中位数？

Question

尝试解决问题 http://www.hackerearth.com/problem/algorithm/sum-of-medians-1/ 并考虑使用多集来解决它，因为它可能包含重复的值。我尝试按如下方式编写代码：

#include<iostream>
#include<set>
#include<algorithm>
using namespace std;
int main()
{
  int n,k,med_sum=0,p;
  cin>>n;
  multiset<int> m;
  multiset<int>::iterator itr;
  for(int i=0;i<n;i++)
  {
    cin>>k;
    m.insert(k);
    p=k;
    if(p<=k)
      itr--;
    else
      itr++;
    med_sum+=*itr;
  }
  cout<<med_sum<<endl;
  return 0;
}

Sample Input:
n=5
10
5
1
2
15
Sample Output: 27
Explanation:
m(1)=median of [10]=10
m(2)=median of [10 5]=5
m(3)=median of [10 5 1]=5
m(4)=median of [10 5 1 2 15]=5
med_sum=10+5+5+2+5=27

Answer 1

匿名用户

如何使用 std：：vector？通过插入 std：：lower_bound 告诉您的位置来保持值的排序。

    std::vector<int> p;
    int k, med_sum;
    while(cin >> k)
    {
      p.insert(std::lower_bound(p.begin(), p.end(), k), k);
      med_sum += p[p.size()/2];
    }
    std::cout << med_sum << std::endl;

编辑< br >使用vector的优点是算法非常清晰简洁(只有3行逻辑),< code>vector内存的缓存局部性和大容量内存分配使其至少比< code > map /< code > set 或< code>list实现更具竞争力，即使其插入是< code>O(n)。

为了进行比较，我使用< code>multiset编写了一个(未测试的)实现:

    std::multiset<int> p;
    int k, med_sum;
    cin >> med_sum;
    p.insert(med_sum);
    std::multiset<int>::iterator itr = p.begin();
    while(cin >> k)
    {
      if(p.size() % 2 == 0)
      {
         if(k < *itr) ++itr;
      }
      else
      {
         if(k < *itr) --itr;
         else ++itr;
      }
      med_sum += *itr;
    }
    cout << med_sum << endl;

这7行逻辑还不错，但它肯定不太清楚发生了什么，我不能只看它是否正确。请注意，此算法仅在< code>C 11中有效，其中< code>multimap::insert在范围(重复值)的顶端插入重复值。

总而言之，我认为< code>vector实现是更好的方法，除非必要性和度量标准要求使用< code>multiset

Answer 2

您似乎试图做的是(错误地，使用您发布的代码)用一个指向中间值的迭代器将值保存在一个多重集中，并在每次添加到集合中时根据您添加的值是高于还是低于中间值来调整指针。

这是一个很好的设计，也可能是解决这个问题最快的方法。但是，它不能与< code>std::multiset一起使用，因为< code>std::multiset的限制导致了一个关键的问题——当添加到集合中的新值等于旧的中值时，您无法知道它是在multiset中旧的中值之前还是之后插入的。所以你无法知道在那种情况下如何调整中值指针。

因此，如果你想以这种方式解决问题，你需要实现你自己的rbtree或其他集合抽象，以一种可以给你这个关键信息的方式。或者，当插入一个等于旧中位数的值时，您可以从头开始细化中位数（这是一个昂贵的操作，但应该很少见）。

编辑

提示 OP 使代码与 C 11 多集一起使用：

>

您需要在将第一个值插入多集时初始化 itr

您只需要在插入itr的“错误”一侧后调整itr。您可以根据多集大小是奇数还是偶数来判断哪一侧是“错误的”。

因为等于旧中值的值将始终插入到< code>itr之后，所以您需要测试< br> if (k

Answer 3

一个简单的方法是维护两个排序容器，一个低于中位数，一个高于中位数。

当你找到一个新元素时，看看要把它插入哪个容器中(这样lower的所有元素总是小于或等于upper的所有元素)，然后重新平衡计数，使中间值在它们之间的“间隙”中。

您的代码可以做到这一点，但是将下限定义为< code>[。begin()、it)和upper to be [it，。end())。我会把它们做成独立的容器，以减少理解代码时需要记住的状态数量，除非性能特别重要。

维护两个排序容器，low和high，具有以下不变量：

• low.size（）与high.size（）相同或大1
• low的每个元素都小于或等于high的每个元素。那么lowUnionhigh的中位数是low.last（）。

假设您有这样一对容器，如果您想添加一个元素< code>x，我将首先保持不变2 - if low.empty()或< code>x

接下来，保持不变1:如果< code>high的元素比low多，则从< code>high中移除最低的元素，并将其添加到< code>low中。如果< code>low比< code>high多2个元素，则从< code>low中移除最高的元素，并将其添加到< code>high中。

如果我们从符合上述两个不变量的< code >低和< code >高开始，那么在上述步骤之后，我们仍然有符合这两个不变量的< code >低和< code >高。而当以上两个不变量成立时，中值就是< code>low.last()！