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