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++ 代码

相关问题

7-1-1 两个有序序列的中位数

在计算机科学和算法设计中，找到两个有序序列的中位数是一个经典问题。假设我们有两个有序序列A和B，长度分别为m和n。我们需要找到这两个序列的中位数。

解决这个问题的一个高效方法是使用二分查找法。具体步骤如下：

1. 确保序列A的长度小于或等于序列B的长度。如果不满足，交换两个序列。
2. 初始化两个指针`imin`和`imax`，分别指向序列A的起始和结束位置。
3. 计算序列A的中间位置`i`，以及序列B的中间位置`j`。
4. 比较A[i]和B[j]：
- 如果A[i] == B[j]，则A[i]（或B[j]）就是中位数。
- 如果A[i] < B[j]，则中位数位于序列A的右半部分和序列B的左半部分。
- 如果A[i] > B[j]，则中位数位于序列A的左半部分和序列B的右半部分。
5. 重复步骤3和4，直到找到中位数。

以下是Python代码示例：

def find_median_sorted_arrays(A, B):
    m, n = len(A), len(B)
    if m > n:
        A, B, m, n = B, A, n, m
    imin, imax, half_len = 0, m, (m + n + 1) // 2
    while imin <= imax:
        i = (imin + imax) // 2
        j = half_len - i
        if i < m and B[j-1] > A[i]:
            imin = i + 1
        elif i > 0 and A[i-1] > B[j]:
            imax = i - 1
        else:
            if i == 0:
                max_of_left = B[j-1]
            elif j == 0:
                max_of_left = A[i-1]
            else:
                max_of_left = max(A[i-1], B[j-1])
            if (m + n) % 2 == 1:
                return max_of_left
            if i == m:
                min_of_right = B[j]
            elif j == n:
                min_of_right = A[i]
            else:
                min_of_right = min(A[i], B[j])
            return (max_of_left + min_of_right) / 2.0

# 示例
A = [1, 3, 5]
B = [2, 4, 6]
print(find_median_sorted_arrays(A, B))

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)。

代码实现：