Trung bình của số K tối đa trong một luồng trong C ++

Giá trị trung bình của số trong một luồng có nghĩa là tính giá trị trung bình sau mỗi lần chèn. Nhưng trong bài toán này, chúng ta cần tìm giá trị trung bình của K số tối đa trong một luồng, tức là chỉ có k số của mảng được xem xét để tính giá trị trung bình. Khi chúng ta thêm một số nếu nó lớn hơn bất kỳ số nào đóng góp vào giá trị trung bình thì chỉ nó được coi là nếu không thì giá trị trung bình vẫn giữ nguyên.

Hãy lấy một ví dụ để hiểu rõ hơn về khái niệm này -

Input : n = 4 , k = 3 , array = { 4, 9, 1 , 5} , stream = {2, 6, 3 , 7 }
Output : 6 , 6.66 , 6.66 , 7.33

Trong lần chèn đầu tiên, giá trị trung bình là 4 + 9 + 5/3 =6, 2 được chèn vào không thay đổi.

Trong lần chèn thứ hai, giá trị trung bình là 6 + 9 + 5/3 =6,66, vì 6 được thêm vào mảng lớn hơn 4 được coi là khi tính giá trị trung bình nên nó được thay thế bằng 6 tạo ra giá trị trung bình là 6,66.

Trong lần chèn thứ ba, giá trị trung bình là 6 + 9 + 5/3 =6,66, 3 được chèn vào không thay đổi.

Ở phần chèn thứ tư, mức trung bình là 6 + 9 + 7/3 =7,33, 7 được chèn vào thay thế cho 5 tạo ra mức trung bình là 7,33.

Bây giờ, vì chúng ta đã biết về bài toán trung bình k số cực đại của một luồng. Hãy tìm ra giải pháp cho vấn đề này. Đối với các vấn đề như thế này, khi việc chèn hoặc xóa các phần tử được thực hiện, chúng tôi sử dụng heap để tìm giải pháp.

Thuật toán

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.

Ví dụ

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);
   }
}

Đầu ra

The sum of K max sums of stream is :
6.0
6.666666666666667
6.666666666666667
7.333333333333333