题目描述
依次读入一个整数序列,每当已经读入的整数个数为奇数时,输出已读入的整数构成的序列的中位数。
输入格式
第一行输入一个整数P,代表后面数据集的个数,接下来若干行输入各个数据集。
每个数据集的第一行首先输入一个代表数据集的编号的整数。
然后输入一个整数M,代表数据集中包含数据的个数,M一定为奇数,数据之间用空格隔开。
数据集的剩余行由数据集的数据构成,每行包含10个数据,最后一行数据量可能少于10个,数据之间用空格隔开。
输出格式
对于每个数据集,第一行输出两个整数,分别代表数据集的编号以及输出中位数的个数(应为数据个数加一的二分之一),数据之间用空格隔开。
数据集的剩余行由输出的中位数构成,每行包含10个数据,最后一行数据量可能少于10个,数据之间用空格隔开。
输出中不应该存在空行。
数据范围
1≤P≤1000,
1≤M≤9999
样例
输入样例:
3
1 9
1 2 3 4 5 6 7 8 9
2 9
9 8 7 6 5 4 3 2 1
3 23
23 41 13 22 -3 24 -31 -11 -8 -7
3 5 103 211 -311 -45 -67 -73 -81 -99
-33 24 56
输出样例:
1 5
1 2 3 4 5
2 5
9 8 7 6 5
3 12
23 23 22 22 13 3 5 5 3 -3
-7 -3
链表离线算法
$O(nlogn)$
思路:对于找中位数,一般思路就是将数组排序后,通过索引直接得到,但是对于本题来说,限制在于每次加入的元素可能会打乱原始排序数组的顺序,由于在数组中插入一个元素的时间复杂度是O(n),因此用这种方式是一定会超时的,而想要在O(1)的时间复杂度插入元素,我们可以想到用链表这种数据结构,于是对于本题来说,就有这样一种离线的链表做法,先将所有元素排序并建成一条双向链表,我们一开始可以确定排序链表中间结点的位置是(n + 1) / 2,然后倒序删除结点,由于链表中的元素是有序的,所以每次删除操作执行后,我们只需要将指针向前或向后移动即可,移动规则可以自己规定,但是要保证当结点数为奇数时,指针指向当前的中位数。
C++ 代码
#include <iostream>
#include <algorithm>
//链表的离线做法:先记下所有数,排序后建成双向链表,倒序操作,每次取中位数后,再删除一个数
using namespace std;
const int N = 1e5, INF = 1e9;
typedef pair<int, int> PII;
typedef long long LL;
PII a[N], p[N];
int l[N], r[N], ans[N];
int m, k, n, mid;
void remove(int cnt, int pos){
int left = l[pos], right = r[pos];
if(cnt % 2){
if(pos >= mid){
mid = l[mid];
}
}
else{
if(pos <= mid){
mid = r[mid];
}
}
r[left] = right, l[right] = left;
}
int main(){
scanf("%d", &m);
while(m--){
scanf("%d %d", &k, &n);
for(int i = 1; i <= n; i++){
scanf("%d", &a[i].first);
a[i].second = i;
}
sort(a + 1, a + n + 1); //按first从小到大排,若first相同按second从小到大排
for(int i = 1; i <= n; i++){
l[i] = i - 1, r[i] = i + 1;
p[a[i].second].first = i; //记录元素在链表中的位置
p[i].second = a[i].first; //记录链表结点代表的值
}
//由于n一定是奇数,因此我们一开始一定可以有一个指针指向链表的中间结点
//之后我们动态维护这个指针,删除的结点有三种情况,要么在指针旁边,要么就是指针的位置,要么是右边
//(1)当结点数为偶数时,若删除的结点在指针位置或左边,指针继承下一个结点,若在指针右边,则位置不变
//(2)当结点数为奇数时,若删除的结点在指针位置或右边,指针继承上一个结点,若在指针左边,则位置不变
mid = (n + 1) / 2; //指针初始位置
int t = 0;
for(int i = n; i >= 1; i--){
if(i % 2){ //是奇数,取中位数
ans[t++] = p[mid].second;
}
remove(i, p[i].first);
}
reverse(ans , ans + t);
printf("%d %d\n", k, t);
int cnt = 0;
for(int i = 0; i < t; i++){
cnt++;
printf("%d ", ans[i]);
if(cnt == 10){
puts("");
cnt = 0;
}
}
if(cnt != 0) puts("");
}
return 0;
}
对顶堆
$O(nlogn)$
blablabla
C++ 代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int N = 1e4 + 5;
//"对顶堆”算法
//序列中从小到大排名为1~M/2的整数存储在大根堆中
//序列中从小到大排名为M/2 + 1 ~ M的整数存储在小根堆中
int a[N]; //中位数序列
int max_heap[N]; //最大堆
int min_heap[N]; //最小堆
int maxhSize, minhSize;
void max_push(int x){
int i;
for(i = ++maxhSize; max_heap[i / 2] < x; i /= 2)
max_heap[i] = max_heap[i / 2];
max_heap[i] = x;
}
void min_push(int x){
int i;
for(i = ++minhSize; min_heap[i / 2] > x; i /= 2)
min_heap[i] = min_heap[i / 2];
min_heap[i] = x;
}
int getMax(){
int Max = max_heap[1];
int last = max_heap[maxhSize--];
int i, Child;
for(i = 1; i * 2 <= maxhSize; i = Child){
Child = i * 2;
if(Child != maxhSize && max_heap[Child + 1] > max_heap[Child]) Child++;
if(last < max_heap[Child]) max_heap[i] = max_heap[Child];
else break;
}
max_heap[i] = last;
return Max;
}
int getMin(){
int Min = min_heap[1];
int last = min_heap[minhSize--];
int i, Child;
for(i = 1; i * 2 <= minhSize; i = Child){
Child = i * 2;
if(Child != minhSize && min_heap[Child + 1] < min_heap[Child]) Child++;
if(last > min_heap[Child]) min_heap[i] = min_heap[Child];
else break;
}
min_heap[i] = last;
return Min;
}
int p, n, m;
int main(void){
scanf("%d", &p);
max_heap[0] = 1e9;
min_heap[0] = -1e9;
while(p--){
minhSize = maxhSize = 0;
scanf("%d %d", &n, &m);
int t = 0, x;
for(int i = 1; i <= m; i++){
scanf("%d", &x);
if(i == 1) min_push(x);
else{
if(x < min_heap[1]) max_push(x);
else min_push(x);
while(minhSize - maxhSize > 2){
max_push(getMin());
}
while(maxhSize - minhSize > -1){
min_push(getMax());
}
}
if(i % 2)a[t++] = min_heap[1];
}
printf("%d %d\n", n, t);
int cnt = 0;
for(int i = 0; i < t; i++){
cnt++;
printf("%d ", a[i]);
if(cnt == 10){
cnt = 0;
puts("");
}
}
if(cnt != 0) puts("");
}
return 0;
}