Trung bình K số lớn nhất trong luồng dữ liệu C++

Cho mảng ban đầu và luồng dữ liệu đến liên tiếp. Sau mỗi lần chèn, tính trung bình của K phần tử lớn nhất hiện có trong mảng.

Ví dụ: n=4, k=3, mảng=[4,9,1,5], luồng=[2,6,3,7] Kết quả: 6, 6.66, 6.66, 7.33

Giải thuật

Sử dụng Min-Heap kích thước K chứa K phần tử lớn nhất. Phần tử nhỏ nhất ở gốc heap. Với mỗi phần tử mới từ luồng: nếu lớn hơn gốc heap, thay thế gốc và cập nhật tổng. Trung bình = tổng / K.

Ví dụ minh họa (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<Integer> 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);
    }
}

Kết quả

6.0
6.666666666666667
6.666666666666667
7.333333333333333