-6
我必須要找到運行中位數按這樣的問題： https://www.hackerrank.com/challenges/ctci-find-the-running-median尋找流動中位數
我想實現兩個堆。存儲小於當前中值的元素的最小堆和存儲大於當前中值的項的最大堆。
中位數不斷變化，並在這兩個堆中元素的個數之差不超過1
我的代碼然而，這不是被接受。但它已經通過了我能想到的測試案例。
請只閱讀主函數和更新中值函數！ 任何幫助表示讚賞。
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
class max_heap{
private:
vector<int> items;
int size;
public:
max_heap(){
size=0;
}
int left(int parent){ return (parent*2 + 1); }
int right(int parent){ return (parent*2 + 2); }
int parent(int pos){ return pos<=0 ? 0 : (pos-1)/2; }
int getmax(){ return items[0]; }
int peek(int pos){ return items[pos];}
int length(){ return items.size();}
void swap(int pos1, int pos2){
int tmp=items[pos1];
items[pos1]=items[pos2];
items[pos2]=tmp;
return;
}
void insert(int key)
{
if(items.size()==size)
items.pb(key);
else
items[size]=key;
//fixing items property
int tmp=size;
while(items[0]!=key && items[parent(tmp)] < key){
swap(parent(tmp), tmp);
tmp=parent(tmp);
}
size++;
}
int pop(){
if(size==0)
return 0;
int ans=getmax();
size--;
items[0]=items[size];
//fix items
int i=0;
while(i<size-1){
bool a = items[i] < items[right(i)];
bool b = items[i] < items[left(i)];
if(a && b)
{
if(items[left(i)] < items[right(i)])
swap(i,left(i));
else swap(i,right(i));
}
else if(a)
swap(i,right(i));
else if(b)
swap(i,left(i));
else break;
}
return ans;
}
void print(){
for (int i = 0; i < items.size(); ++i)
cout<<items[i]<<" ";
cout<<endl;
}
};
class min_heap{
private:
vector<int> items;
int size;
public:
min_heap(){
size=0;
}
int left(int parent){ return (parent*2 + 1); }
int right(int parent){ return (parent*2 + 2); }
int parent(int pos){ return pos<=0 ? 0 : (pos-1)/2; }
int getmin(){ return items[0]; }
int peek(int pos){ return items[pos];}
int length(){ return items.size();}
void swap(int pos1, int pos2){
int tmp=items[pos1];
items[pos1]=items[pos2];
items[pos2]=tmp;
return;
}
void insert(int key)
{
if(items.size()==size)
items.pb(key);
else
items[size]=key;
//fixing items property
int tmp=size;
while(items[0]!=key && items[parent(tmp)] > key){
swap(parent(tmp), tmp);
tmp=parent(tmp);
}
size++;
}
int pop(){
if(size==0)
return 0;
int ans=getmin();
size--;
items[0]=items[size];
//fix items
int i=0;
while(i<size-1){
bool a = items[i] > items[right(i)];
bool b = items[i] > items[left(i)];
if(a && b)
{
if(items[left(i)] < items[right(i)])
swap(i,left(i));
else swap(i,right(i));
}
else if(a)
swap(i,right(i));
else if(b)
swap(i,left(i));
else break;
}
return ans;
}
void print(){
for (int i = 0; i < items.size(); ++i)
cout<<items[i]<<" ";
cout<<endl;
}
};
double update_median(int element, int median, min_heap &mn_heap, max_heap &mx_heap)
{
int path = mx_heap.length() - mn_heap.length();
double ans=0.0;
switch(path){
case 0:
if(element > median){
//push to right heap..ie the min heap
mn_heap.insert(element);
ans= mn_heap.getmin();
}
else
{
//push to left heap....ie max heap
mx_heap.insert(element);
ans= mx_heap.getmax();
}
break;
case 1: //max heap is greater ie left
if(element > median)
{ //push to right heap...min heap
mn_heap.insert(element);
ans=(mn_heap.getmin() + mx_heap.getmax())/2.0;
}
else
{
mn_heap.insert(mx_heap.pop());
mx_heap.insert(element);
ans= (mn_heap.getmin() + mx_heap.getmax())/2.0;
}
break;
case -1: // min heap greater ie right
if(element > median)
{ //push to right heap...min heap
mx_heap.insert(mn_heap.pop());
mn_heap.insert(element);
ans=(mn_heap.getmin() + mx_heap.getmax())/2.0;
}
else
{
mx_heap.insert(element);
ans= (mn_heap.getmin() + mx_heap.getmax())/2.0;
}
break;
}
return ans;
}
int main(){
cout.sync_with_stdio(false);
int el;
cin>>el;
double median=0.0;
min_heap *a = new min_heap(); //items less than median
max_heap *b = new max_heap(); //items more than median
while(el--){
int element;
cin>>element;
median= update_median(element,median,*a,*b);
printf("%.1lf\n", median);
}
}
歡迎來到Stack Overflow。請花些時間閱讀[The Tour]（http://stackoverflow.com/tour），並參閱[幫助中心]（http://stackoverflow.com/help/asking）中的資料，瞭解您可以在這裏問。 –
解決這些問題的正確工具是您的調試器。在*堆棧溢出問題之前，您應該逐行執行您的代碼。如需更多幫助，請閱讀[如何調試小程序（由Eric Lippert撰寫）]（https://ericlippert.com/2014/03/05/how-to-debug-small-programs/）。至少，您應該\編輯您的問題，以包含一個[最小，完整和可驗證]（http://stackoverflow.com/help/mcve）示例，該示例再現了您的問題，以及您在調試器。 –
如果兩個堆之間的差異永遠不會超過1，那麼您只需要保留每個堆的一個元素。 – stark