C++ 中运行数据流的中位数

在这个问题中，我们得到一个持续读取整数的数据流。我们的任务是创建一个程序，读取元素并计算这些元素的中位数。

中位数是指从排序后的序列（可以是升序或降序）中取出的中间元素。

计算中位数

对于奇数个数，中位数是中间元素

对于偶数个数，中位数是两个中间元素的平均值

让我们举个例子来理解这个问题：

输入 - 3, 65, 12, 20, 1

在每个输入时：

Input - 3 : sequence -(3) : median - 3
Input - 65 : sequence -(3, 65) : median - 34
Input - 12 : sequence -(3, 12, 65) : median - 12
Input - 20 : sequence -(3, 12, 20, 65) : median - 16
Input - 1 : sequence -(1, 3, 12, 20, 65) : median - 12

我们在这里使用了排序后的序列，以便于计算中位数。

为了解决这个问题，我们有多种解决方案，例如在每一步都进行排序然后找到中位数、创建自平衡二叉搜索树或使用堆。堆似乎是找到中位数最有效的解决方案。最大堆或最小堆都可以在每次插入时提供中位数，并且也是一种有效的解决方案。

示例

展示我们解决方案实现的程序：

 在线演示

#include <iostream>
using namespace std;
#define MAX_HEAP_SIZE (128)
#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])
void swap(int &a, int &b){
   int temp = a;
   a = b;
   b = temp;
}
bool Greater(int a, int b){
   return a > b;
}
bool Smaller(int a, int b){
   return a < b;
}
int Signum(int a, int b){
   if( a == b )
      return 0;
   return a < b ? -1 : 1;
}
class Heap{
   public:
      Heap(int *b, bool (*c)(int, int)) : A(b), comp(c)
      { heapSize = -1; }
      virtual bool Insert(int e) = 0;
      virtual int GetTop() = 0;
      virtual int ExtractTop() = 0;
      virtual int GetCount() = 0;
      protected:
      int left(int i) {
         return 2 * i + 1;
      }
      int right(int i) {
         return 2 * (i + 1);
      }
      int parent(int i) {
         if( i <= 0 ){
            return -1;
         }
         return (i - 1)/2;
      }
      int *A;
      bool (*comp)(int, int);
      int heapSize;
      int top(void){
         int max = -1;
         if( heapSize >= 0 )
            max = A[0];
         return max;
      }
      int count() {
         return heapSize + 1;
      }
      void heapify(int i){
         int p = parent(i);
         if( p >= 0 && comp(A[i], A[p]) ) {
            swap(A[i], A[p]);
            heapify(p);
         }
      }
      int deleteTop(){
         int del = -1;
         if( heapSize > -1){
            del = A[0];
            swap(A[0], A[heapSize]);
            heapSize--;
            heapify(parent(heapSize+1));
         }
         return del;
      }
      bool insertHelper(int key){
         bool ret = false;
         if( heapSize < MAX_HEAP_SIZE ){
            ret = true;
            heapSize++;
            A[heapSize] = key;
            heapify(heapSize);
         }
         return ret;
      }
};
class MaxHeap : public Heap {
   private:
   public:
      MaxHeap() : Heap(new int[MAX_HEAP_SIZE], &Greater) { }
      int GetTop() {
         return top();
      }
      int ExtractTop() {
         return deleteTop();
      }
      int GetCount() {
         return count();
      }
      bool Insert(int key) {
         return insertHelper(key);
      }
};
class MinHeap : public Heap{
   private:
   public:
      MinHeap() : Heap(new int[MAX_HEAP_SIZE], &Smaller) { }
      int GetTop() {
         return top();
      }
      int ExtractTop() {
         return deleteTop();
      }
      int GetCount() {
         return count();
      }
      bool Insert(int key) {
         return insertHelper(key);
      }
};
int findMedian(int e, int &median, Heap &left, Heap &right){
   switch(Signum(left.GetCount(), right.GetCount())){
      case 0: if( e < median ) {
         left.Insert(e);
         median = left.GetTop();
      }
      else{
         right.Insert(e);
         median = right.GetTop();
      }
      break;
      case 1: if( e < median ){
         right.Insert(left.ExtractTop());
         left.Insert(e);
      }
      else
         right.Insert(e);
         median = ((left.GetTop()+right.GetTop())/2);
      break;
      case -1: if( e < median )
         left.Insert(e);
      else {
         left.Insert(right.ExtractTop());
         right.Insert(e);
      }
      median = ((left.GetTop()+right.GetTop())/2);
      break;
   }
   return median;
}
void printMedianStream(int A[], int size){
   int median = 0;
   Heap *left = new MaxHeap();
   Heap *right = new MinHeap();
   for(int i = 0; i < size; i++) {
      median = findMedian(A[i], median, *left, *right);
      cout<<"Median of elements : ";
      for(int j = 0; j<=i;j++) cout<<A[j]<<" ";
      cout<<"is "<<median<<endl;
   }
}
int main(){
   int A[] = {12, 54, 9, 6, 1};
   int size = ARRAY_SIZE(A);
   printMedianStream(A, size);
   return 0;
}

输出

Median of elements : 12 is 12
Median of elements : 12 54 is 33
Median of elements : 12 54 9 is 12
Median of elements : 12 54 9 6 is 10
Median of elements : 12 54 9 6 1 is 9

Narendra Kumar

更新于: 2020-06-03

309 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习