算法：寻找两个等长有序序列的中位数

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法：寻找两个等长有序序列的中位数，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2016字，纯文字阅读大概需要3分钟。

内容图文

题目：寻找两个等长有序序列的中位数
【问题描述】对于一个长度为n的有序序列（假设均为升序序列）a[0…n-1]，处于中间位置的元素称为a的中位数。设计一个算法求给定的两个有序序列的中位数
【例子】如序列a=(11,13,15,17,19)，其中位数是15，t若b=(2,4,6,8,20)，其中位数为6.两个等长有序序列的中位数是含它们所有元素的x有序序列的中位数，例如a，b两个有序序列的中位数为11。
a=(11,13,15,17,19)，b=(2,4,6,8,20) => c=(2,4,6,8,(11),12,15,17,19,20)

#include <stdio.h>

int findMedian(int[],int,int,int[],int,int);

int main() {

int n;
int a[10],b[10];

printf("请输入序列长度:");       //输入序列长度
scanf("%d",&n);
printf("请输入长度为%d的两个序列:\n",n);        //输入两个等长序列
for(int i = 0; i < n; i++) {
    scanf("%d",&a[i]);
}
for(int i = 0; i < n; i++) {
    scanf("%d",&b[i]);
}

int x = findMedian(a, 0, n-1, b, 0, n-1);
printf("%d\n",x);      //输出所有数的中位数


return 0;

}

int findMedian(int a[],int i,int j,int b[],int m,int n) { //主要思想：分别取两个序列1，2（假设为升序序列）的中位数a，b，如果a<b，说明序列1中位数左边的序列肯定不为所有数的中位数，就在下一次递归中删去左边部分；同理，说明序列2中位数右边的序列肯定不为所有数的中位数。

int p = ( i + j ) / 2;      //取中位数
int q = ( m + n ) / 2;

if( a[p] == b[q] ) {       //当两个序列的中位数相等时即所有数的中位数
    return a[p];
}

if( j == i && n == m ) {     //当两个序列最后只剩一个数，取x较小值作为所有数的中位数
    if( a[i] < b[m] ) return a[i];
    else return b[m];
}


if ( a[p] < b[q] ) {      //当a<b,在下一次递归中删去a的左边部分，b的右边部分
    if( j-1 == i )       //值得注意的是，因为数组的下标都是整数，所以取中位数的下标只能为首下标与尾下标的向下取整，导致了当两个序列分别剩两个数的时候，取平均数永远无法改变导致死循环。举例，当序列1还剩3，4两个数，中位数为3，序列2还剩6，7两个数，中位数为7时，因为3<7，所以下次递归的序列应该为序列1：4，序列2：6，但由于取整的原因序列1的下标无法指向4，导致出错。
        p += 1;
    return findMedian(a, p, j, b, m, q);
    
}else if( a[p] > b[q] ) {      //当a>b,在下一次递归中删去a的右边部分，b的左边部分
    if( n-1 == m )
        q += 1;
    return findMedian(a, i, p, b, q, n);
    
}

return 0;

}

内容总结

以上是互联网集市为您收集整理的算法：寻找两个等长有序序列的中位数全部内容，希望文章能够帮你解决算法：寻找两个等长有序序列的中位数所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---