資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++資料流中查詢中位數
假設我們有一個數據流，在這個資料流中，一些資料元素可能會加入，我們需要建立一個系統來幫助查詢資料的中位數。眾所周知，中位數是有序列表中間的資料，如果列表長度為奇數，可以直接得到中位數；否則，取中間兩個元素，然後求平均值。因此，將有兩種方法：addNum() 和 findMedian()，這兩種方法將用於將數字新增到流中，並查詢所有已新增數字的中位數。
為了解決這個問題，我們將遵循以下步驟：
定義優先順序佇列 left 和 right
定義 addNum 方法，該方法將數字作為輸入：
如果 left 為空或 num < left 的頂部元素，則：
將 num 插入 left
否則
將 num 插入 right
如果 left 的大小 < right 的大小，則：
temp := right 的頂部元素
從 right 刪除元素
將 temp 插入 left
如果 left 的大小 – right 的大小 > 1，則：
temp := left 的頂部元素
從 left 刪除元素
將 temp 插入 right
定義 findMedian() 方法，該方法將按如下方式工作：
如果 left 的大小 > right 的大小，則返回 left 的頂部元素；否則返回 (left 的頂部元素 + right 的頂部元素) / 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
更新於：2020年5月27日
373 次檢視
廣告