C++의 데이터 스트림에서 중앙값 찾기

데이터 스트림이 있다고 가정하고 해당 스트림에서 일부 데이터 요소가 와서 결합할 수 있으며 데이터에서 중앙값을 찾는 데 도움이 되는 하나의 시스템을 만들어야 합니다. 중앙값이 정렬된 목록의 중간 데이터라는 것을 알고 있으므로 목록 길이가 홀수이면 중앙값을 직접 얻을 수 있고 그렇지 않으면 중간 두 요소를 취한 다음 평균을 찾을 수 있습니다. 따라서 addNum() 및 findMedian()의 두 가지 메서드가 있으며 이 두 메서드는 스트림에 숫자를 추가하고 추가된 모든 숫자의 중앙값을 찾는 데 사용됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 왼쪽 및 오른쪽 우선 순위 대기열 정의

• addNum 메소드를 정의하십시오. 이것은 숫자를 입력으로 사용합니다 -

• 왼쪽이 비어 있거나 num <왼쪽의 맨 위 요소인 경우

  • 왼쪽에 숫자 삽입

• 그렇지 않으면

  • 오른쪽에 숫자 삽입

• 왼쪽의 크기 <오른쪽의 크기인 경우

  • temp :=오른쪽 상단

  • 오른쪽에서 항목 삭제

  • 왼쪽에 임시 삽입

• 왼쪽의 크기 - 오른쪽의 크기> 1인 경우

  • temp :=왼쪽 상단

  • 왼쪽에서 항목 삭제

  • 오른쪽에 임시 삽입

• findMedian() 메서드를 정의하면 다음과 같이 작동합니다. -

  • 왼쪽의 크기> 오른쪽의 크기인 경우 왼쪽 상단 반환, 그렇지 않으면 (왼쪽 상단 + 오른쪽 상단)/2

예

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
typedef double lli;
class MedianFinder {
   priority_queue <int> left;
   priority_queue <int, vector <int>, greater<int>> right;
   public:
   void addNum(int num) {
      if(left.empty() || num<left.top()){
         left.push(num);
      }else right.push(num);
      if(left.size()<right.size()){
         lli temp = right.top();
         right.pop();
         left.push(temp);
      }
      if(left.size()-right.size()>1){
         lli temp = left.top();
         left.pop();
         right.push(temp);
      }
   }
   double findMedian() {
      return
      left.size()>right.size()?left.top():(left.top()+right.top())*0.5;
   }
};
main(){
   MedianFinder ob;
   ob.addNum(10);
   ob.addNum(15);
   cout << ob.findMedian() << endl;
   ob.addNum(25);
   ob.addNum(30);
   cout << ob.findMedian() << endl;
   ob.addNum(40);
   cout << ob.findMedian();
}

입력

addNum(10);
addNum(15);
findMedian();
addNum(25);
addNum(30);
findMedian();
addNum(40);
findMedian();

출력

12.5
20
25