ค่าเฉลี่ยของตัวเลขในสตรีมหมายถึงการคำนวณค่าเฉลี่ยหลังจากการแทรกทุกครั้ง แต่ในปัญหานี้ เราต้องหาค่าเฉลี่ยของตัวเลข 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 max ของสตรีมแล้ว มาหาวิธีแก้ปัญหานี้กัน สำหรับปัญหาเช่นนี้ เมื่อมีการแทรกหรือลบองค์ประกอบ เราใช้ฮีปเพื่อค้นหาวิธีแก้ปัญหา
อัลกอริทึม
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
