Chương trình tìm ra giá trị trung bình của một mảng số nguyên trong C ++

Giả sử chúng ta phải triển khai một lớp có tên là MedianClass chứa các phương thức sau -

• add (value) để thêm một giá trị vào cấu trúc dữ liệu.

• median () tìm giá trị trung bình của tất cả các số hiện có trong cấu trúc dữ liệu.

Vì vậy, nếu chúng ta thêm 5, 3, 8 và tìm trung vị, kết quả sẽ là 5,0, sau đó nếu chúng ta thêm 9 và tìm trung vị, kết quả sẽ là 6,5.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định hàng đợi ưu tiên bên trái và bên phải

• Xác định phương thức addNum, phương thức này sẽ lấy số làm đầu vào -

• nếu bên trái để trống hoặc num

  • chèn num vào bên trái

• Nếu không

  • chèn num vào bên phải

• nếu kích thước của trái

  • temp:=phần tử trên cùng của bên phải

  • xóa mục khỏi bên phải

  • chèn tạm thời vào bên trái

• nếu kích thước của trái - kích thước của phải> 1, thì

  • temp:=phần tử trên cùng bên trái

  • xóa mục từ bên trái

  • chèn tạm thời vào bên phải

• Xác định phương thức findMedian (), phương thức này sẽ hoạt động như sau -

return top of left if size of left> size of right, else (trên cùng bên trái + trên cùng bên phải) / 2Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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

Đầu vào

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

Đầu ra

5.0
6.5