Tìm Trung bình từ Luồng dữ liệu trong C ++

Giả sử chúng ta có một luồng dữ liệu, trong luồng đó một số phần tử dữ liệu có thể đến và tham gia, chúng ta phải tạo một hệ thống, điều đó sẽ giúp tìm ra giá trị trung bình từ dữ liệu. Như chúng ta biết rằng trung vị là dữ liệu giữa của một danh sách đã sắp xếp, nếu độ dài danh sách là lẻ, chúng ta có thể lấy trung vị trực tiếp, nếu không thì lấy hai phần tử ở giữa, sau đó tìm giá trị trung bình. Vì vậy, sẽ có hai phương thức, addNum () và findMedian (), hai phương thức này sẽ được sử dụng để thêm các số vào luồng và tìm giá trị trung bình của tất cả các số được thêm vào

Để 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 -

  • trả về trên cùng bên trái nếu kích thước của trái> kích thước của phải, khác (trên cùng bên trái + trên cùng của bên phải) / 2

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

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

Đầu ra

12.5
20
25