किसी स्ट्रीम में औसत संख्या का अर्थ है प्रत्येक प्रविष्टि के बाद औसत की गणना करना। लेकिन इस समस्या में, हमें एक धारा में अधिकतम 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