스트림에 있는 숫자의 평균은 모든 삽입 후 평균을 계산하는 것을 의미합니다. 그러나 이 문제에서는 스트림에서 최대 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입니다. 4보다 큰 배열에 6을 더하면 평균 계산 시 고려되므로 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