C++ में स्ट्रीम में अधिकतम K संख्याओं का औसत

समस्या विवरण

एक स्ट्रीम में आने वाली संख्याओं में से हर बार अधिकतम K संख्याओं का औसत निकालें। जब नई संख्या आए, यदि यह वर्तमान K अधिकतम संख्याओं में से किसी से बड़ी है, तो उसे शामिल करें और औसत अपडेट करें।

उदाहरण

n=4, k=3, array={4,9,1,5}, stream={2,6,3,7}

• प्रारंभिक: 4,9,5 का औसत = 6
• 2 जोड़ने पर: कोई परिवर्तन नहीं, औसत = 6
• 6 जोड़ने पर: 4 की जगह 6, औसत = 6.66
• 3 जोड़ने पर: कोई परिवर्तन नहीं, औसत = 6.66
• 7 जोड़ने पर: 5 की जगह 7, औसत = 7.33

हल दृष्टिकोण

मिन हीप का उपयोग करें जिसमें K अधिकतम तत्व हों। रूट सबसे छोटा होगा। प्रत्येक नई संख्या के लिए, यदि यह रूट से बड़ी है तो रूट को बदलें।

उदाहरण कोड (Java)

import java.util.*;

public class Kmaxsum {
    static void maxAverageKNumbers(int n, int k, int m, int[] arr, int[] query) {
        double maxAvg = 0.0;
        PriorityQueue pq = new PriorityQueue<>();
        Arrays.sort(arr);
        double sum = 0;
        
        for (int i = n - 1; i >= n - k; i--) {
            pq.add(arr[i]);
            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 + query[i];
            }
            maxAvg = sum / (double)k;
            System.out.println(maxAvg);
        }
    }
    
    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};
        maxAverageKNumbers(n, k, m, arr, query);
    }
}

आउटपुट

6.0
6.666666666666667
6.666666666666667
7.333333333333333