PeekMedian -- return the median value of all the elements in the stack. With N elements,
the median value is defined to be the (N/2)-th smallest element if N is even, or ((N+1)/2)-th
if N is odd.
中间的数,当N为偶数的时候就是最小的第N/2个数,即要从小到大排序,第几个数
法一:sort
$TLE$ 用vector
模拟栈的操作,栈的push
对应push_back
,pop
对应pop_back
,median
对应 排序后找中位数
时间复杂度:N = 1e5次询问,排序N*logN=2e6,O(2e11),最终PAT只过了两个数据
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> stk;
int n;
void push(int x)
{
stk.push_back(x);
}
void pop()
{
if (stk.empty())
{
puts("Invalid");
return;
}
int len = stk.size();
printf("%d\n", stk[len-1]);
stk.pop_back();
}
void peek()
{
if (stk.empty())
{
puts("Invalid");
return;
}
int len = stk.size();
vector<int>a(stk);
sort(a.begin(), a.end());
if (len&1 == 1) printf("%d\n", a[len/2]); //奇数
else printf("%d\n", a[(len-1) / 2]);
}
int main()
{
scanf("%d", &n);
while (n--)
{
char op[20];
scanf("%s", op);
if (op[1] == 'u')
{
int x;
scanf("%d", &x);
push(x);
}
else if (op[1] == 'o')
pop();
else peek();
}
return 0;
}
法二:lower_bound
stk
进行push
,pop
操作,在push的同时将数插到对应的vector
中,vector用来维护栈中所有元素排好序的结果。
时间复杂度:N=1e5次操作,push,pop都是O(N),median是O(logN),总$O(1e10)$
vector<int> a;
lower_bound(a.begin(), a.end(), x); //返回大于等于x的地址
a.insert(lower_bound(a.begin(), a.end(), x), x); //可以让a有序插入元素
a.erase(lower_bound(a.begin(), a.end(), x), x); //删除一个x
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
stack<int> stk;
vector<int> a;
int n;
void Push(int x)
{
stk.push(x);
a.insert(lower_bound(a.begin(), a.end(), x), x); //将x插到vector中的正确位置,使其有序
}
void Pop()
{
if (stk.empty())
{
puts("Invalid");
return;
}
printf("%d\n", stk.top());
a.erase(lower_bound(a.begin(), a.end(), stk.top())); //删去大于等于栈顶的第一个元素
stk.pop();
}
void Peek()
{
if (stk.empty())
{
puts("Invalid");
return;
}
int len = a.size();
if (len&1 == 1) printf("%d\n", a[len/2]); //奇数
else printf("%d\n", a[(len-1) / 2]);
}
int main()
{
scanf("%d", &n);
while (n--)
{
char op[20];
scanf("%s", op);
if (op[1] == 'u')
{
int x;
scanf("%d", &x);
Push(x);
}
else if (op[1] == 'o')
Pop();
else Peek();
}
return 0;
}
对顶堆
所有数一分为二,上面为大于等于x的数,下面为小于等于x的数。下面数的个数要么等于上面的数,要么比上面的数量多1。
上面的数用小根堆维护,下面的用大根堆维护,堆顶就是中位数。每次插入一个数与下面大根堆的堆顶对比,若是大于等于插到上面,小于等于插到下面,然后再调整上下的数量。
删除元素用堆不太好维护,这里用平衡树multiset
来维护,有序,操作都是O(logN),multiset可以含有重复元素,set不可以。上下大小根堆换成multiset
。
时间复杂度:O(N*logN)=1e6
#include <iostream>
#include <stack>
#include <set>
#include <cstring>
using namespace std;
stack<int> stk;
multiset<int> up, down; //up:大于中位数的小根堆, down:小于中位数的大根堆,下面数量等于上面或者为上面+1
int n;
void adjust()
{
while (up.size() > down.size()) //上面的堆多
{
//把上面的小根堆堆顶移到下面
auto t = up.begin(); //迭代器
down.insert(*t); //加到下面
up.erase(t); //删去迭代器,不需要加*
}
while (down.size() > up.size() + 1) //下面的堆多
{
//把下面的大根堆堆顶移到上面
auto t = down.end();
t--;
up.insert(*t);
down.erase(t);
}
}
int main()
{
scanf("%d", &n);
while (n--)
{
char op[15];
scanf("%s", op);
if (!strcmp(op, "Push"))
{
int x;
scanf("%d", &x);
stk.push(x);
//先判断能否插到下面的大根堆中,即判断x是否小于小根堆的堆顶,
//若小根堆堆顶不存在,也插到下面去
if (up.empty() || x < *up.begin()) //up.begin()返回最小元素(第一个元素)的迭代器(地址),加*为元素值
down.insert(x);
else up.insert(x);
adjust(); //调整
}
else if (!strcmp(op, "Pop"))
{
if (stk.empty()) puts("Invalid");
else
{
int t = stk.top();
stk.pop();
printf("%d\n", t);
//判断t在上面还是下面,上面可能为空,但下面绝对不为空
auto it = down.end(); //下面的大根堆堆顶
it--; //end为迭代器末尾,但不是最后一个数,所以要--
if (t <= *it) //若t <= 下面的大根堆堆顶,就删除下面的数
down.erase(down.find(t)); //只删除一个t,所以加find,不加就删除所有t
else up.erase(up.find(t));
adjust();
}
}
else
{
if (stk.empty()) puts("Invalid");
else
{
//中位数就是下面大根堆顶
auto t = down.end();
t--;
printf("%d\n", *t);
}
}
}
return 0;
}
感谢博主提供的思路,方法二挺好的,不过还是有一组数据通不过
感谢提醒(虽然一年多没碰,我现在都看不懂自己写的了