資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
廣告