7-2 两个有序序列的中位数 (25 分)

题目描述：

给定两个长度为n的有序序列A和B，本题要求时间复杂度为O(logn)的算法，找出两个序列的中位数。

输入格式：

第一行输入一个整数n，表示序列的长度。

第二行输入n个整数，表示序列A。

第三行输入n个整数，表示序列B。

输出格式：

输出一个整数，表示两个序列的中位数。

输入样例：

5
1 3 5 7 9
2 4 6 8 10

输出样例：

5

解题思路：

中位数的定义是：将一个集合分成两个长度相等的子集，其中一个子集中的元素总是大于另一个子集中的元素。根据这个定义，我们可以将两个有序序列分别划分成两个长度相等的子集，使得一个子集中的元素总是大于另一个子集中的元素。假设序列A和序列B的长度都为n，我们可以将序列A和序列B分别划分成两个长度为n/2的子序列，分别为A1、A2和B1、B2。如果A1的中位数小于B1的中位数，那么A1中的元素肯定都小于两个序列的中位数，因此可以将A1中的元素全部舍去，将A2和B1、B2组成新的序列，继续进行划分。如果A1的中位数大于B1的中位数，那么B1中的元素肯定都小于两个序列的中位数，因此可以将B1中的元素全部舍去，将A1、A2和B2组成新的序列，继续进行划分。如果A1的中位数等于B1的中位数，那么A1和B1中的元素都小于两个序列的中位数，因此可以将A1、B1和A2、B2组成新的序列，继续进行划分。每次划分后，序列的长度都会减半，因此时间复杂度为O(logn)。

代码实现：

相关问题

7-1 两个有序序列的中位数 (25 分)

题目描述：

给定两个长度分别为m和n的有序序列，求其中位数。

输入格式：

第一行输入一个整数m，表示第一个有序序列的长度。

第二行输入m个整数，表示第一个有序序列。

第三行输入一个整数n，表示第二个有序序列的长度。

第四行输入n个整数，表示第二个有序序列。

输出格式：

输出一个整数，表示两个有序序列的中位数。

输入样例：

5
1 3 5 7 9
6
2 4 6 8 10 12

输出样例：

7

算法1：

(二分查找) $O(log(min(m,n)))$

1.先确定中位数的位置，如果m+n为奇数，则中位数位置为(m+n+1)/2，如果为偶数，则中位数位置为(m+n)/2和(m+n)/2+1。

2.在两个有序序列中分别进行二分查找，找到第一个序列中第k/2个数和第二个序列中第k/2个数，比较两个数的大小，如果第一个序列中的数小，则第一个序列中前k/2个数都不可能是中位数，将第一个序列中前k/2个数舍去，更新k值，继续在剩下的数中查找中位数。

3.重复步骤2，直到找到中位数。

时间复杂度

二分查找的时间复杂度为O(log(min(m,n)))，因此总时间复杂度为O(log(min(m,n)))。

C++ 代码

算法2：

(归并排序) $O(m+n)$

1.将两个有序序列合并成一个有序序列。

2.如果合并后的序列长度为奇数，则中位数为合并后序列的中间位置的数，如果长度为偶数，则中位数为中间位置的两个数的平均值。

时间复杂度

归并排序的时间复杂度为O(m+n)，因此总时间复杂度为O(m+n)。

C++ 代码

pta7-52两个有序序列的中位数

要找到两个有序序列pta7和52的中位数，首先需要将这两个序列合并为一个有序序列。然后，根据合并后的序列长度的奇偶性来确定中位数的位置。

如果合并后的序列长度为奇数，中位数的位置就在序列的中间，即第 (n+1)/2 个位置上，其中n是合并后序列的长度。

如果合并后的序列长度为偶数，中位数的位置就在第 n/2 和 (n/2+1) 个位置上，这时需要取这两个位置上的数的平均值作为中位数。

按照以上方法，计算出pta7和52两个有序序列合并后的序列，并根据序列长度的奇偶性找到中位数的位置，最终确定出中位数的数值。

需要注意的是，由于pta7和52两个序列是有序的，合并后的序列则应该是一个有序序列。合并后再计算中位数的步骤是需要耐心和准确的。