数据结构:
√N个块block[0,...,√N - 1],范围是从[k*√N,(k+1)*√N - 1],查询的范围[0,N-1]
缺点:适用于一个确定范围的插入删除+查询
image.png相当于维护一个能返回中位数同时支持插入和删除的数据结构。
插入与删除:
Sign数组记录下标对应的数字的重复次数,
Block记录block范围内的数字的出现次数之和。
- 一个数A插入时,int Sign[A]++,int Block[A/sqrtN]++
- 当A要删除的时候,int Sign[A]--,int Block[A/sqrtN]--
举个例子:
// 已存在的元素{0,1,3,4,4,5,8}
最高是8,所以取9,如果是9,则取16。
// block作为块
block[0]=2 // 0,1
block[1]=4 // 3,4,4,5
block[2]=1 // 8
// table记录同一个值有多少重复的元素
table[0]=1;
table[1]=1;
table[2]=0;
table[3]=1;
table[4]=2;
table[5]=1;
table[6]=0;
示例代码:
#include <bits/stdc++.h>
using namespace std;
// 最大值
#define N 100010
// 块的大小
const int sqrtN=316;
vector<int>s;
int block[N]={0};
// 存储块的数据,设为sqrtN会报错....
int table[N]={0};
// 存储对应取值的数据
void findMedian(){
if(s.empty()){
cout<<"Invalid"<<endl;
return;
}
int i,j;
int counts=0;
int target=0;
if(s.size()&1){
// 奇数
target=(s.size()+1)/2;
}
else{
// 偶数
target=s.size()/2;
}
for(i=0;i<sqrtN;i++){
counts+=block[i];
if(counts>=target){
counts-=block[i];
// 计算第K个值可能的开始-结束的值
int bottom=i*sqrtN;
int hign=(i+1)*sqrtN-1;
for(j=bottom;j<=hign;j++){
counts+=table[j];
if(counts>=target){
printf("%d\n",j);
return ;
}
}
}
}
}
void Push(int num){
table[num]++;
block[num/sqrtN]++;
s.push_back(num);
}
void Popup(){
if(s.empty()){
printf("Invalid\n");
return;
}
int tp=s[s.size()-1];
s.pop_back();
// 点值--
table[tp]--;
// 块值--
block[tp/sqrtN]--;
printf("%d\n",tp);
}
int main(){
int i,j;
int times;
char input[100];
char Pop[]="Pop";
char PeekMedian[]="PeekMedian";
scanf("%d\n",×);
// 必须摘去\n要不然会影响到后面的读取
// 书上的方法只是在该用例输入的时候可以投机取巧,字符串处理最好还是cin.getline(input,N)+string的方式
for(i=0;i<times;i++){
scanf("%s",input);
// 要判断字符串相等需要用string==string,但是用char[]+strcmp更省钱
if(strcmp(input,Pop)==0){
Popup();
}
else if(strcmp(input,PeekMedian)==0){
findMedian();
}
else{
int num;
scanf("%d",&num);
Push(num);
}
}
}
/*
17
Pop
PeekMedian
Push 3
PeekMedian
Push 2
PeekMedian
Push 1
PeekMedian
Pop
Pop
Push 5
Push 4
PeekMedian
Pop
Pop
Pop
Pop
*/
网友评论