中位数
题面题面描述输入输出
算法分析暴力暴力思路核心代码
链表链表思路
链表+贪心链表+贪心思路核心代码
题面
题面描述
输入一个奇数
n
n
n和长度为
n
n
n的数组
a
a
a，请你求出
a
a
a数组前
1
,
3
,
5
…
…
n
1,3,5……n
1,3,5……n个数的中位数 注：多组数据
输入
第一行 一个数
p
p
p，表示有
p
p
p组数据 下一行，两个数
k
k
k和
n
n
n，表示是第
k
k
k组 接下来若干行，每行
10
10
10个数，共
n
n
n个数
输出
第一行输出
k
k
k和中位数的个数
(
(
(通常为
n
/
2
+
1
n/2+1
n/2+1
)
)
) 接下输出中位数，
10
10
10个数一换行
p
≤
1000
p\le1000
p≤1000
n
≤
9999
n\le9999
n≤9999
算法分析
暴力
暴力思路
每输入奇数个数就拍一次序，简单一算，直接TLE
核心代码
for(int i
=1; i
<=N
; i
++) {
scanf("%d",&a
[i
]);
if(1&i
){
sort(a
+1,a
+1+i
);
printf("%d "a
[i
/2+1]);
if(i
%10==0||i
==N
)printf("\n");
}
链表
链表思路
将所有排序后，用链表模拟倒序删除 剩下是奇数个时，查找中位数 极端数据还是被卡
链表+贪心
链表+贪心思路
在链表的基础上，判断删除的数
两个都小于上一个中位数两个一个大于，一个小于上一个中位数两个都大于上一个中位数
中位数往后中位数不动中位数向前
核心代码
scanf("%d%d",&K
,&N
);
for(int i
=1; i
<=N
; i
++) {
l
[i
]=i
-1;
r
[i
]=i
+1;
}
l
[N
+1]=N
,r
[0]=1;
X
=N
/2+1;
for(iKt i
=1; i
<=N
; i
++) {
scanf("%d",&a
[i
]);
num
[i
]=a
[i
];
}
sort(a
+1,a
+1+N
);
ans
[X
]=X
;
for(int i
=1; i
<X
; i
++) {
for(int j
=1; j
<=N
; j
=r
[j
]) {
if(num
[N
-i
*2+2]==a
[j
]) {
w
[0]=j
;
break;
}
}
for(int j
=1; j
<=N
; j
=r
[j
]) {
if(num
[N
-i
*2+1]==a
[j
]) {
w
[1]=j
;
break;
}
}
l
[r
[w
[0]]]=l
[w
[0]],r
[l
[w
[0]]]=r
[w
[0]];
l
[r
[w
[1]]]=l
[w
[1]],r
[l
[w
[1]]]=r
[w
[1]];
if(num
[N
-i
*2+2]>=a
[ans
[X
-i
+1]]&&num
[N
-i
*2+1]>=a
[ans
[X
-i
+1]]) {
ans
[X
-i
]=l
[ans
[X
-i
+1]];
} else if(Kum
[N
-i
*2+2]<=a
[ans
[X
-i
+1]]&&Kum
[N
-i
*2+1]<=a
[ans
[X
-i
+1]]) {
ans
[X
-i
]=r
[ans
[X
-i
+1]];
} else {
ans
[X
-i
]=ans
[X
-i
+1];
}
}
printf("%d %d\n",K
,X
);
for(int i
=1; i
<=X
; i
++) {
if(i
!=1)printf("%d ",a
[ans
[i
]]);
else printf("%d ",num
[1]);
if(i
%10==0||i
==X
)printf("\K");
}
