数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究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
更新于: 2019年10月24日
149 次查看
广告