C++のストリーム内の最大K数の平均

ストリーム内の数の平均は、挿入するたびに平均を計算することを意味します。しかし、この問題では、ストリーム内の最大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は変更なしで挿入されました。

2番目の挿入では、平均は6 + 9 + 5/3 =6.66です。これは、平均の計算で考慮される4より大きい配列に6が追加され、6に置き換えられて平均6.66になるためです。

3回目の挿入では、平均は6 + 9 + 5/3 =6.66であり、3回挿入しても変化はありません。

4番目の挿入では、平均は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