知识付费网站开发教程,做网站 工资高吗,建网站地址,南昌建网站单位2#xff0c;4#xff0c;6#xff0c;8#xff0c;11#xff0c;13#xff0c;15#xff0c;17#xff0c;19#xff0c;20
可以推出题目的一个隐含条件#xff1a;偶数个元素的中位数是靠前的那一个
应试技巧#xff1a;如果实在想不出高效的算法#xff0c;那…
2468111315171920
可以推出题目的一个隐含条件偶数个元素的中位数是靠前的那一个
应试技巧如果实在想不出高效的算法那么就把笨办法写上不能空卷
注意读题是两个等长数组 奇数个元素的时候只能删除中位数之前的 当ab时中位数ab A2681011 B3581213 排序23568810111213 当ab时a8b10 假设AB如下 A2681011 B35101315 A删除中位数左边的B删除中位数右边的 A81011 B3510 此时a10b5abA删除中位数右边的B删除中位数左边的 A810 B510 此时元素A和B的元素个数都为偶数个则删除大的那个中位数右边的元素删除小的那个中位数及它前面的元素a8b5则A删掉10B删掉它自己的中位数b5 A8 B10 最后取小的那个数即可即中位数8下面可以验证出是正确的 235681010111315 当ab时类似推理即可 代码
#include stdio.h
int MidSearch(int A[],int B[],int n)
{int s1,s2,d1,d2,m1,m2;s1s20;d1d2n-1;while(s1!d1 s2!d2){m1 (s1 d1)/2;m2 (s2 d2)/2;if(A[m1]A[m2]){return A[m1];//满足条件两个数组的中位数相等}if(A[m1]A[m2]){//满足条件abif((s1s2)%20){ //若元素个数为奇数,这里注意数组下标从0开始s1m1; //舍弃 A 中间点以前的部分且保留中间点d2m2; //舍弃 B 中间点以后的部分且保留中间点}else{ //元素个数为偶数s1m11;//舍弃 A 中间点及中间点以前部分d2m2; //舍弃 B 中间点以后部分且保留中间点}}else{ //满足条件abif((s1s2)%20){ //若元素个数为奇数d1m1; //舍弃 A 中间点以后的部分且保留中间点s2m2; //舍弃 B 中间点以前的部分且保留中间点}else{ //元素个数为偶数d1m1; //舍弃 A 中间点以后部分且保留中间点s2m21;//舍弃 B 中间点及中间点以前部分}}}return A[s1]B[s2]?A[s1]:B[s2];
}
int main()
{int A[] {2,6,8,10,11};int B[] {3,5,8,12,13};int mid MidSearch(A,B,5);printf(mid %d\n,mid);return 0;
}
mid 8
