স্ট্রিমে সংখ্যার গড় বলতে প্রতিটি ইনসারশনের পর গড় বের করা হয়। কিন্তু এই সমস্যাতিতে আমাদের স্ট্রিমে সর্বোচ্চ 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, ২ যোগ হলে কোনো পরিবর্তন নেই।
- দ্বিতীয় ইনসারশনে গড় = (6+9+5)/3 = 6.66, ৬ যোগ হলে ৪-এর স্থানে ৬ বসে গড় ৬.৬৬ হয়।
- তৃতীয় ইনসারশনে গড় = ৬.৬৬, ৩ যোগ হলে পরিবর্তন নেই।
- চতুর্থ ইনসারশনে গড় = (6+9+7)/3 = 7.33, ৭ যোগ হলে ৫-এর স্থানে ৭ বসে গড় ৭.৩৩ হয়।
অ্যালগরিদম
Step 1: অ্যারেতে K সর্বোচ্চ উপাদান নিয়ে একটি মিন হিপ তৈরি করুন (K উপাদানের মধ্যে সবচেয়ে ছোটটি রুটে থাকবে)। Step 2: স্ট্রিমের প্রতিটি উপাদানের জন্য: Step 3: উপাদানটি হিপের রুটের সাথে তুলনা করুন। Step 4: যদি রুট উপাদান থেকে ছোট হয়, তবে রুটকে নতুন উপাদান দিয়ে প্রতিস্থাপন করুন।
উদাহরণ কোড (Java)
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, k = 3, m = 4;
int[] arr = {4, 9, 1, 5};
int[] query = {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
