算法

2023-11-23 08:38| 来源: 网络整理| 查看: 265

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

目录寻找两个等长有序序列的中位数【问题描述】【算法讲解】【完整代码】【运行结果】

【问题描述】

对于一个长度为n的有序序列（假设均为升序序列）a[0…n-1]，处于中间位置的元素称为a的中位数。设计一个算法求给定的两个有序序列的中位数。

例如，若序列a=(11，13，15，17，19)，其中位数是15，若b=(2，4，6，8，20)，其中位数为6。两个等长有序序列的中位数是含它们所有元素的有序序列的中位数。例如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)

【算法讲解】

对于含有n个元素的有序序列a[s…t]，当n为奇数时，中位数是出现在m=(s+t)/2处；当n为偶数时，中位数下标有m=(s+t)/2（下中位）和m=(s+t)/2+1（上中位）两个。为了简单，仅考虑中位数为m=(s+t)/2处。在这里插入图片描述采用二分法求解。分别求出 a，b 的中位数 a[m1]，b[m2]：情形1：若a[m1]=b[m2]，则a[m1]或b[m2]即为所求中位数，算法结束。情形2：若a[m1]b[m2]，则舍弃序列a中后半部分（较大的一半），同时舍弃序列b中前半部分（较小的一半），要求舍弃的长度相等。

【完整代码】

VS2017 C++

#include using namespace std; #define MAXN 15 //取a[s..t]序列的前半个子序列 void prepart(int& s, int& t) { int m = (s + t) / 2; t = m; } //取a[s..t]序列的后半个子序列 void backpart(int& s, int& t) { int m = (s + t) / 2; //序列中有奇数个元素 if ((s + t) % 2 == 0) s = m; //序列中有偶数个元素 else s = m + 1; } //求中位数 int midnum(int a[], int s1, int t1, int b[], int s2, int t2) { int m1, m2; if (s1 == t1 && s2 == t2) return a[s1] backpart(s1, t1);//序列1取后半部分 prepart(s2, t2);//序列2取前半部分 return midnum(a, s1, t1, b, s2, t2); } else { backpart(s2, t2);//序列2取后半部分 prepart(s1, t1);//序列1取前半部分 return midnum(a, s1, t1, b, s2, t2); } } } int main() { int n; int a[MAXN], b[MAXN]; cout n; cout

【本文地址】

公司简介

联系我们