C++에서 정수 배열의 중앙값을 찾는 프로그램

다음 메소드를 포함하는 MedianClass라는 클래스를 구현해야 한다고 가정합니다. -

• 데이터 구조에 값을 추가하는 add(value).

• median()은 데이터 구조에 현재 존재하는 모든 숫자의 중앙값을 찾습니다.

따라서 5, 3, 8을 더하고 중앙값을 찾으면 출력은 5.0이 되고 9를 더하고 중앙값을 찾으면 출력은 6.5가 됩니다.

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

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

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

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

  • 왼쪽에 숫자 삽입

• 그렇지 않으면

  • 오른쪽에 숫자 삽입

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

  • temp :=오른쪽 상단 요소

  • 오른쪽에서 항목 삭제

  • 왼쪽에 임시 삽입

• 왼쪽의 크기 - 오른쪽의 크기> 1이면

  • temp :=왼쪽 상단 요소

  • 왼쪽에서 항목 삭제

  • 오른쪽에 임시 삽입

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

return top of left if left> size of right, else (top of left + top of right)/2더 나은 이해를 위해 다음 구현을 보자 -

예시

#include <bits/stdc++.h>
using namespace std;
typedef double lli;
class MedianClass {
   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(){
   MedianClass ob;
   ob.addNum(5);
   ob.addNum(3);
   ob.addNum(8);
   cout << ob.findMedian() << " ";
   ob.addNum(9);
   cout << ob.findMedian() << endl;
}

입력

ob.addNum(5);
ob.addNum(3);
ob.addNum(8);
cout << ob.findMedian() << endl;
ob.addNum(9);
cout << ob.findMedian() << endl;

출력

5.0
6.5