C ++流中最大K个数的平均值

流中数字的平均值表示每次插入后计算平均值。但是在这个问题中，我们需要找到一个流中最大K个数的平均值，即仅考虑数组中的k个数来计算平均值。如果我们添加的数字大于构成平均值的任何数字，则仅考虑该数字，否则平均值保持不变。

让我们举个例子来更好地理解这个概念-

Input : n = 4 , k = 3 , array = { 4, 9, 1 , 5} , stream = {2, 6, 3 , 7 }
Output : 6 , 6.66 , 6.66 , 7.33

在第一次插入中，平均值为4 + 9 + 5/3 = 6，其中2个插入没有变化。

在第二次插入中，平均值为6 + 9 + 5/3 = 6.66，因为将6添加到大于4的数组中，这在计算平均值时会被考虑，因此将其替换为6，从而得出平均值6.66。

在第三次插入中，平均值为6 + 9 + 5/3 = 6.66，其中3个插入没有变化。

在第四次插入中，平均值为6 + 9 + 7/3 = 7.33，插入的7取代了5，得出平均值为7.33。

现在，由于我们知道了流的最大k个最大数量的问题。让我们得出这个问题的解决方案。对于这样的问题，在执行元素插入或删除的情况下，我们使用堆来查找解决方案。

算法

Step 1 : create a min heap of K Max elements of the array. ( the smallest of the K elements is at the root).
Step 2 : for every element of the stream. Do :
Step 3 : Compare the element with the root of the heap.
Step 4 : If root is less than element then replace the root with new element.

示例

import java.util.*;
public class Kmaxsum {
   static void max_average_k_numbers(int n, int k, int m, int[] arr, int[] query){
      double max_avg = 0.0;
      PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
      Arrays.sort(arr);
      double sum = 0;
      for (int i = n - 1; i >= n - k; i--) {
         pq.add(arr[i]);
         sum = sum + arr[i];
      }
      for (int i = 0; i < m; i++) {
         if (query[i] > pq.peek()) {
            int polled = pq.poll();
            pq.add(query[i]);
            sum = sum - polled;
            sum = sum + query[i];
         }
         max_avg = sum / (double)k;
         System.out.println(max_avg);
      }
   }
   public static void main(String[] args){
      int n = 4;
      int k = 3;
      int m = 4;
      int[] arr = new int[] { 4, 9, 1 , 5 };
      int[] query = new int[] { 2, 6, 3 , 7 };
      System.out.println("The sum of K max sums of stream is : ");
      max_average_k_numbers(n, k, m, arr, query);
   }
}

输出结果

The sum of K max sums of stream is :
6.0
6.666666666666667
6.666666666666667
7.333333333333333