একটি প্রবাহে সংখ্যার গড় মানে প্রতিটি সন্নিবেশের পরে গড় গণনা করা। কিন্তু এই সমস্যায়, আমাদের একটি স্ট্রীমে সর্বাধিক 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
