代码之家 › 专栏 › 技术社区 › Satish Patel

如何跟踪整数变化向量的中值?

stl algorithm c++

Satish Patel · 技术社区 · 11 年前

试图在解决问题 http://www.hackerearth.com/problem/algorithm/sum-of-medians-1/ 并考虑使用multiset来解决问题,因为它可能包含重复的值。我尝试按如下方式进行编码:

#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

3 回复 | 直到 11 年前

Yakk - Adam Nevraumont 11 年前

一个简单的方法是维护两个分类的容器,一个比中位数低,一个更大。

当你找到一个新元素时,看看要把它插入哪个容器(这样所有较低的元素总是小于或等于所有较高的元素),然后重新平衡计数,这样中位数就在它们之间的“中间”。

您的可以这样做,但将较低的范围定义为 [.begin(), it) 和鞋面 [it, .end()) 。除非性能特别重要,否则我会将它们制作成单独的容器,以减少您在理解代码时需要记住的状态量。

维护两个已分拣的容器, low 和 high ,具有以下不变量:

low.size() 与 high.size() 或大于1
的每一个元素 低的 小于或等于的每个元素 高的 . 然后是 低的 协会 高的 是 low.last() .

假设你有这样一对容器,如果你想添加一个元素 x ,我将首先保持不变量2-如果 low.empty() 或 x <= low.last() ,插进去 低的 ,否则将其粘牢 高的 .

接下来,保持不变1:如果 高的 元素多于低元素,请从中删除最低元素 高的 并将其添加到 低的 如果 低的 比多2个元素 高的 ,从中删除最高元素 低的 并将其添加到 高的 .

如果我们从 低的 和 高的 遵循上述两个不变量,那么在上述步骤之后,我们仍然有 低的 和 高的 服从这两个不变量。当上述两个不变量成立时,中值为 低.last() !

Chris Dodd 11 年前

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

这是一个很好的设计,可能也是解决这个问题最快的方法。然而,它不适用于 std::multiset 由于 标准::多集 这就导致了一个关键的角点情况的问题——当添加到集合中的新值等于旧中值时,你无法知道它是在多集合中的旧中值之前还是之后插入的。所以在这种情况下,你不知道如何调整中间指针。

因此,如果你想以这种方式解决问题,你需要实现你自己的rbtree或其他集合抽象,以提供这一关键信息。或者,当插入一个等于旧中值的值时,可以从头开始对中值进行再融资(这是一种昂贵的操作,但应该很少)。

编辑

提示OP使代码与C++11多集一起工作:

您需要初始化 itr 将第一个值插入多集时
你只需要调整一下 单位面积 在的“错误”一侧插入后 单位面积 。你可以根据多集大小是奇数还是偶数来判断哪一边“错了”。
由于总是在后面插入一个等于旧中值的值 单位面积 你想要考试吗
if (k < *itr) 不 <=

SirGuy 11 年前

用一个怎么样 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;

编辑
使用矢量的优点是算法非常清晰和简洁(只有3行逻辑) vector 的内存和大容量内存分配使其与 map / set 或 list 实现,即使其插入是 O(n) .

为了进行比较,我使用 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行逻辑还不错,但肯定不太清楚发生了什么,我不能仅仅通过看它来判断它是否正确。请注意,此算法仅适用于 C++11 哪里 multimap::insert 在(重复项)范围的顶端插入重复值。

总而言之,我认为 矢量 实现是更好的方法,除非必要性和衡量标准要求 多重集合