使用STL计算运行整数流的中值-yiteyi-C++库

假设从数据流中读取整数。求从第一个整数到最后一个整数为止读取的所有元素的中值。这也被称为运行整数的中值。数据流可以是任何数据源，例如，文件、整数数组、输入流等。

null

什么是中位数？

中位数可以定义为数据集中将数据样本的上半部分与下半部分分开的元素。换句话说，我们可以得到中间元素，当输入大小为奇数时，我们取排序数据的中间元素。如果输入大小为偶数，则我们在排序的流中选取中间两个元素的平均值。 例如：

输入： 5 10 15 输出： 5, 7.5, 10 解释：给定输入流为整数数组[5,10,15]。逐个读取整数，并相应地打印中值。所以，在读取第一个元素5之后，中位数是5。阅读10后，中位数为7.5，阅读15后，中位数为10。 输入： 1, 2, 3, 4 输出： 1, 1.5, 2, 2.5 解释：给定输入流为整数数组[1,2,3,4]。逐个读取整数，并相应地打印中值。所以，在读取第一个元素1之后，中位数是1。阅读2后，中位数为1.5，阅读3后，中位数为2。读数为4后，中位数为2.5。

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

方法： 其思想是使用max-heap和min-heap来存储上半部分和下半部分的元素。最大堆和最小堆可以使用优先级队列在C++ STL中。下面是解决这个问题的逐步算法。 算法：

创建两个堆。一个最大堆用于在任何时间点维护下半部分的元素，一个最小堆用于维护上半部分的元素。。
取中值的初始值为0。
对于每个新读取的元素，将其插入最大堆或最小堆，并根据以下条件计算中值：
- 如果最大堆的大小大于最小堆的大小，并且元素小于之前的中位数，则从最大堆中弹出顶部元素并插入到最小堆中，然后将新元素插入到最大堆中，否则将新元素插入到最小堆中。将新的中值计算为最大和最小堆元素顶部的平均值。
- 如果最大堆的大小小于最小堆的大小，并且元素大于之前的中位数，则从最小堆中弹出顶部元素并插入到最大堆中，然后将新元素插入到最小堆中，否则将新元素插入到最大堆中。将新的中值计算为最大和最小堆元素顶部的平均值。
- 如果两个堆的大小相同。然后检查电流是否小于先前的中值。如果当前元素小于之前的中值，则将其插入最大堆，新的中值将等于最大堆的顶部元素。如果当前元素大于上一中位数，则将其插入最小堆，新的中位数将等于最小堆的顶部元素。

下面是上述方法的实现。

C++

                         // C++ program to find med in                       
                         // stream of running integers                       
                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // function to calculate med of stream                       
                         void                                     printMedians(                                     double                                     arr[],                                     int                                     n)                       
                         {                       
                                                 // max heap to store the smaller half elements                       
                                                 priority_queue<                                     double                                     > s;                       
           
                                                 // min heap to store the greater half elements                       
                                                 priority_queue<                                     double                                     ,vector<                                     double                                     >,greater<                                     double                                     > > g;                       
           
                                                 double                                     med = arr[0];                       
                                                 s.push(arr[0]);                       
           
                                                 cout << med << endl;                       
           
                                                 // reading elements of stream one by one                       
                                                 /*  At any time we try to make heaps balanced and                       
                                                 their sizes differ by at-most 1. If heaps are                       
                                                 balanced,then we declare median as average of                       
                                                 min_heap_right.top() and max_heap_left.top()                       
                                                 If heaps are unbalanced,then median is defined                       
                                                 as the top element of heap of larger size  */                       
                                                 for                                     (                                     int                                     i=1; i < n; i++)                       
                                                 {                       
                                                 double                                     x = arr[i];                       
           
                                                 // case1(left side heap has more elements)                       
                                                 if                                     (s.size() > g.size())                       
                                                 {                       
                                                 if                                     (x < med)                       
                                                 {                       
                                                 g.push(s.top());                       
                                                 s.pop();                       
                                                 s.push(x);                       
                                                 }                       
                                                 else                       
                                                 g.push(x);                       
           
                                                 med = (s.top() + g.top())/2.0;                       
                                                 }                       
           
                                                 // case2(both heaps are balanced)                       
                                                 else                                     if                                     (s.size()==g.size())                       
                                                 {                       
                                                 if                                     (x < med)                       
                                                 {                       
                                                 s.push(x);                       
                                                 med = (                                     double                                     )s.top();                       
                                                 }                       
                                                 else                       
                                                 {                       
                                                 g.push(x);                       
                                                 med = (                                     double                                     )g.top();                       
                                                 }                       
                                                 }                       
           
                                                 // case3(right side heap has more elements)                       
                                                 else                       
                                                 {                       
                                                 if                                     (x > med)                       
                                                 {                       
                                                 s.push(g.top());                       
                                                 g.pop();                       
                                                 g.push(x);                       
                                                 }                       
                                                 else                       
                                                 s.push(x);                       
           
                                                 med = (s.top() + g.top())/2.0;                       
                                                 }                       
           
                                                 cout << med << endl;                       
                                                 }                       
                         }                       
           
                         // Driver program to test above functions                       
                         int                                     main()                       
                         {                       
                                                 // stream of integers                       
                                                 double                                     arr[] = {5, 15, 10, 20, 3};                       
                                                 int                                     n =                                     sizeof                                     (arr)/                                     sizeof                                     (arr[0]);                       
                                                 printMedians(arr, n);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find med in                       
                         // stream of running integers                       
                         import                                     java.util.Collections;                       
                         import                                     java.util.PriorityQueue;                       
           
                         public                                     class                                     MedianMaintain                       
                         {                       
                                   
                                                 // method to calculate med of stream                       
                                                 public                                     static                                     void                                     printMedian(                                     int                                     [] a)                       
                                                 {                       
                                   
                                                 double                                     med = a[                                     0                                     ];                       
                                   
                                                 // max heap to store the smaller half elements                       
                                                 PriorityQueue<Integer> smaller =                                     new                                     PriorityQueue<>                       
                                                 (Collections.reverseOrder());                       
                                   
                                                 // min-heap to store the greater half elements                       
                                                 PriorityQueue<Integer> greater =                                     new                                     PriorityQueue<>();                       
                                   
                                                 smaller.add(a[                                     0                                     ]);                       
                                                 System.out.println(med);                       
                                   
                                                 // reading elements of stream one by one                       
                                                 /* At any time we try to make heaps balanced and                       
                                                 their sizes differ by at-most 1. If heaps are                       
                                                 balanced,then we declare median as average of                       
                                                 min_heap_right.top() and max_heap_left.top()                       
                                                 If heaps are unbalanced,then median is defined                       
                                                 as the top element of heap of larger size */                       
                                                 for                                     (                                     int                                     i =                                     1                                     ; i < a.length; i++)                       
                                                 {                       
                                   
                                                 int                                     x = a[i];                       
                                   
                                                 // case1(left side heap has more elements)                       
                                                 if                                     (smaller.size() > greater.size())                       
                                                 {                       
                                                 if                                     (x < med)                       
                                                 {                       
                                                 greater.add(smaller.remove());                       
                                                 smaller.add(x);                       
                                                 }                       
                                                 else                       
                                                 greater.add(x);                       
                                                 med = (                                     double                                     )(smaller.peek() + greater.peek())/                                     2                                     ;                       
                                                 }                       
                                   
                                                 // case2(both heaps are balanced)                       
                                                 else                                     if                                     (smaller.size() == greater.size())                       
                                                 {                       
                                                 if                                     (x < med)                       
                                                 {                       
                                                 smaller.add(x);                       
                                                 med = (                                     double                                     )smaller.peek();                       
                                                 }                       
                                                 else                       
                                                 {                       
                                                 greater.add(x);                       
                                                 med = (                                     double                                     )greater.peek();                       
                                                 }                       
                                                 }                       
                                   
                                                 // case3(right side heap has more elements)                       
                                                 else                       
                                                 {                       
                                                 if                                     (x > med)                       
                                                 {                       
                                                 smaller.add(greater.remove());                       
                                                 greater.add(x);                       
                                                 }                       
                                                 else                       
                                                 smaller.add(x);                       
                                                 med = (                                     double                                     )(smaller.peek() + greater.peek())/                                     2                                     ;                       
                                   
                                                 }                       
                                                 System.out.println(med);                       
                                                 }                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main(String []args)                       
                                                 {                       
                                   
                                                 // stream of integers                       
                                                 int                                     [] arr =                                     new                                     int                                     []{                                     5                                     ,                                     15                                     ,                                     10                                     ,                                     20                                     ,                                     3                                     };                       
                                                 printMedian(arr);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Kaustav kumar Chanda.                       

C#

                         // C# program to find med in                       
                         // stream of running integers                       
                         using                                     System;                       
                         using                                     System.Collections.Generic;                       
                         public                                     class                                     MedianMaintain                       
                         {                       
           
                                                 // method to calculate med of stream                       
                                                 public                                     static                                     void                                     printMedian(                                     int                                     [] a)                       
                                                 {                       
                                                 double                                     med = a[0];                       
           
                                                 // max heap to store the smaller half elements                       
                                                 List<                                     int                                     > smaller =                                     new                                     List<                                     int                                     >();                       
           
                                                 // min-heap to store the greater half elements                       
                                                 List<                                     int                                     >  greater =                                     new                                     List<                                     int                                     >();                       
                                                 smaller.Add(a[0]);                       
                                                 Console.WriteLine(med);                       
           
                                                 // reading elements of stream one by one                       
                                                 /* At any time we try to make heaps balanced and                       
                                                 their sizes differ by at-most 1. If heaps are                       
                                                 balanced,then we declare median as average of                       
                                                 min_heap_right.top() and max_heap_left.top()                       
                                                 If heaps are unbalanced,then median is defined                       
                                                 as the top element of heap of larger size */                       
                                                 for                                     (                                     int                                     i = 1; i < a.Length; i++)                       
                                                 {                       
           
                                                 int                                     x = a[i];                       
           
                                                 // case1(left side heap has more elements)                       
                                                 if                                     (smaller.Count > greater.Count)                       
                                                 {                       
                                                 if                                     (x < med)                       
                                                 {                       
                                                 smaller.Sort();                       
                                                 smaller.Reverse();                       
                                                 greater.Add(smaller[0]);                       
                                                 smaller.RemoveAt(0);                       
                                                 smaller.Add(x);                       
                                                 }                       
                                                 else                       
                                                 greater.Add(x);                       
                                                 smaller.Sort();                       
                                                 smaller.Reverse();                       
                                                 greater.Sort();                       
                                                 med = (                                     double                                     )(smaller[0] + greater[0])/2;                       
                                                 }                       
           
                                                 // case2(both heaps are balanced)                       
                                                 else                                     if                                     (smaller.Count == greater.Count)                       
                                                 {                       
                                                 if                                     (x < med)                       
                                                 {                       
                                                 smaller.Add(x);                       
                                                 smaller.Sort();                       
                                                 smaller.Reverse();                       
                                                 med = (                                     double                                     )smaller[0];                       
                                                 }                       
                                                 else                       
                                                 {                       
                                                 greater.Add(x);                       
                                                 greater.Sort();                       
                                                 med = (                                     double                                     )greater[0];                       
                                                 }                       
                                                 }                       
           
                                                 // case3(right side heap has more elements)                       
                                                 else                       
                                                 {                       
                                                 if                                     (x > med)                       
                                                 {                       
                                                 greater.Sort();                       
                                                 smaller.Add(greater[0]);                       
                                                 greater.RemoveAt(0);                       
                                                 greater.Add(x);                       
                                                 }                       
                                                 else                       
                                                 smaller.Add(x);                       
                                                 smaller.Sort();                       
                                                 smaller.Reverse();                       
                                                 med = (                                     double                                     )(smaller[0] + greater[0])/2;                       
           
                                                 }                       
                                                 Console.WriteLine(med);                       
                                                 }                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main(String []args)                       
                                                 {                       
           
                                                 // stream of integers                       
                                                 int                                     [] arr =                                     new                                     int                                     []{5, 15, 10, 20, 3};                       
                                                 printMedian(arr);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Rajput-Ji                       

Javascript

                         <script>                       
                         // Javascript program to find med in                       
                         // stream of running integers                       
           
                         // method to calculate med of stream                       
                         function                                     printMedian(a)                       
                         {                       
                                                 let med = a[0];                       
                                   
                                                 // max heap to store the smaller half elements                       
                                                 let smaller = [];                       
                                   
                                                 // min-heap to store the greater half elements                       
                                                 let greater = [];                       
                                   
                                                 smaller.push(a[0]);                       
                                                 document.write(med+                                     "<br>"                                     );                       
                                                 // reading elements of stream one by one                       
                                                 /* At any time we try to make heaps balanced and                       
                                                 their sizes differ by at-most 1. If heaps are                       
                                                 balanced,then we declare median as average of                       
                                                 min_heap_right.top() and max_heap_left.top()                       
                                                 If heaps are unbalanced,then median is defined                       
                                                 as the top element of heap of larger size */                       
                                                 for                                     (let i = 1; i < a.length; i++)                       
                                                 {                       
                                   
                                                 let x = a[i];                       
                                   
                                                 // case1(left side heap has more elements)                       
                                                 if                                     (smaller.length > greater.length)                       
                                                 {                       
                                                 if                                     (x < med)                       
                                                 {                       
                                                 smaller.sort(                                     function                                     (a,b){                                     return                                     b-a;});                       
                                   
                                                 greater.push(smaller.shift());                       
                                                 smaller.push(x);                       
                                                 }                       
                                                 else                       
                                                 {    greater.push(x);}                       
                                                 smaller.sort(                                     function                                     (a,b){                                     return                                     b-a;});                       
                                                 greater.sort(                                     function                                     (a,b){                                     return                                     a-b;});                       
                                                 med = (smaller[0] + greater[0])/2;                       
                                   
                                                 }                       
                                   
                                                 // case2(both heaps are balanced)                       
                                                 else                                     if                                     (smaller.length == greater.length)                       
                                                 {                       
                                                 if                                     (x < med)                       
                                                 {                       
                                                 smaller.push(x);                       
                                                 smaller.sort(                                     function                                     (a,b){                                     return                                     b-a;});                       
                                   
                                                 med = smaller[0];                       
                                                 }                       
                                                 else                       
                                                 {                       
                                                 greater.push(x);                       
                                   
                                                 greater.sort(                                     function                                     (a,b){                                     return                                     a-b;});                       
                                                 med = greater[0];                       
                                                 }                       
                                                 }                       
                                   
                                                 // case3(right side heap has more elements)                       
                                                 else                       
                                                 {                       
                                                 if                                     (x > med)                       
                                                 {                       
                                   
                                                 greater.sort(                                     function                                     (a,b){                                     return                                     a-b;});                       
                                                 smaller.push(greater.shift());                       
                                                 greater.push(x);                       
                                                 }                       
                                                 else                       
                                                 {                       
                                                 smaller.push(x);}                       
                                                 smaller.sort(                                     function                                     (a,b){                                     return                                     b-a;});                       
                                   
                                                 med = (smaller[0] + greater[0])/2;                       
                                   
                                                 }                       
                                   
                                                 document.write(med+                                     "<br>"                                     );                       
                                   
                                                 }                       
                         }                       
           
                         // Driver code                       
                         // stream of integers                       
                         let arr=[5, 15, 10, 20, 3];                       
                         printMedian(arr);                       
           
                         // This code is contributed by avanitrachhadiya2155                       
                         </script>                       

输出：

5101012.510

复杂性分析：

时间复杂性： O（n logn）。在最小堆中插入元素的时间复杂度是logn，所以插入n元素的时间复杂度是O（n logn）。
辅助空间： O（n）。在堆中存储元素所需的空间是O（n）。

本文由 维布加格 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章