資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中查詢整數陣列中位數的程式
假設我們必須實現一個名為 MedianClass 的類，其中包含以下方法：
add(value)：將值新增到資料結構中。
median()：查詢當前資料結構中所有數字的中位數。
因此，如果我們新增 5、3、8 並查詢中位數，則輸出將為 5.0，然後如果我們新增 9 並查詢中位數，則輸出將為 6.5。
為了解決這個問題，我們將遵循以下步驟：
定義優先佇列 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 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
更新於： 2020-12-26
219 次檢視
廣告